Replica predictions hold for the minimum matching problem in the pseudo-dimension d mean field model for d>=1.

You need to know: Graph, complete graph, matching in a graph, minimum matching, limits, notation $P$ for probability, random variable, independent random variables, distribution, density.

Background: Let $d>0$ be a real number, and let $n>0$ be an even integer. In a complete graph $G_n$ on n vertices, let each edge $e$ be assigned independent random cost $C_e$ from a fixed distribution on the non-negative real numbers with density $\rho(t)$ , such that $\lim\limits_{t \to 0^+} \frac{\rho(t)}{dt^{d-1}} = 1$ . Let $M(n,d)$ be the (random) cost of a minimum matching in $G_n$ .

The Theorem: On 1st July 2009, Johan Wästlund submitted to the Annals of Mathematics a paper in which he proved that for any $d \geq 1$ there exists a number $\beta(d)$ such that for any $\epsilon>0$ , $\lim\limits_{n\to \infty}P\left[\left|M(n,d) - \beta(d)\right|>\epsilon\right] = 0.$

Short context: Minimum matching problem in a graph is one of the fundamental problems in graph theory. A model in which the edge costs are randomly chosen as described above is known as the mean field model of pseudo-dimension d. In 1985, Mézard and Parisi introduced non-rigorous analysis with physical origin (called replica analysis) which allowed them to predict that the statement of the Theorem holds for any $d>0$ , write down a conjectured analytic formula for $\beta(d)$ , and compute it numerically. However, before 2009, these predictions were rigorously confirmed only for $d=1$ . The Theorem did this for all $d\geq 1$ .