Title: An easy proof of the $\zeta(2)$ limit in the random assignment problem
Abstract:The edges of the complete bipartite graph $K_{n,n}$ are given independent exponentially distributed costs. Let $C_n$ be the minimum total cost of a perfect matching. It was conjectured by M. Mézard an...The edges of the complete bipartite graph $K_{n,n}$ are given independent exponentially distributed costs. Let $C_n$ be the minimum total cost of a perfect matching. It was conjectured by M. Mézard and G. Parisi in 1985, and proved by D. Aldous in 2000, that $C_n$ converges in probability to $\pi^2/6$. We give a short proof of this fact, consisting of a proof of the exact formula $1 + 1/4 + 1/9 + \dots + 1/n^2$ for the expectation of $C_n$, and a $O(1/n)$ bound on the variance.Read More