The Minimum Perfect Matching in Pseudo-dimension $0<q<1$

Abstract

It is known that for $K_{n,n}$ equipped with i.i.d. $exp(1)$ edge costs, the minimum total cost of a perfect matching converges to ${\pi }^2/6$ in probability. Similar convergence has been established for all edge cost distributions of pseudo-dimension $q\ge 1$, such as Wei(1,q) costs. In this paper we extend those results all $q>0$, confirming the Mézard-Parisi conjecture in the last remaining applicable case.

arXiv commentRevised journal version, to appear in 'Combinatorics, Probability and Computing'