Replica symmetry of the minimum matching


We establish the soundness of the replica symmetric ansatz introduced by M. Mézard and G. Parisi for the minimum matching problem in the pseudo-dimension $d$ mean field model for $d\geq 1$. The case $d=1$ corresponds to the $\pi^2/6$-limit for the assignment problem proved by D. Aldous in 2001.
We introduce a game-theoretical framework by which we establish the analogous limit also for $d>1$.


Johan Wästlund

Department of Mathematical Sciences, Chalmers University of Technology and Gothenburg University, SE-412 96 Gothenburg, Sweden