Bipartite matching and Van der Waerden conjecture

In this paper I show that the free energy F and the cost C associated to a bipartite matching problem can be explicitly estimated in term of the solution of a suitable system of equations (cavity equations in the following). The proof of these results relies on a well known result in combinatorics: the Van der Waerden conjecture (Egorychev-Falikman Theorem). Cavity equations, derived by a mean field argument by Mezard and Parisi, can be considered as a smoothed form of the dual formulation for the bipartite matching problem. Moreover cavity equation are the Euler-Lagrange equations of a convex functional G parameterized by the temperature T. In term of their unique solution it is possible to define a free-energy-like function of the temperature g(T). g is a strictly decreasing concave function of T and C = g(0). The convexity of G allows to define an explicit algorithm to find the solution of the cavity equations at a given temperature T. Moreover, once the solution of the cavity equations at a given temperature T is known, the properties of g allow to find exact estimates from below and from above of the cost C.