probability-statistics / Random combinatorial optimization

Central limit theorem for the random assignment problem

Let $C_n$ be the minimum cost of a perfect matching in an $n\times n$ matrix of independent uniform random variables. Aldous proved in 1992 that $\mathbb{E}[C_n]$ converges, later identifying the limit as $\zeta(2)$ via the Poisson-weighted infinite tree; Parisi's exact finite-$n$ formula for exponential costs was then proved by Linusson-Wästlund and independently by Nair, Prabhakar and Sharma. The fluctuations resisted. Talagrand applied product-space concentration, Wästlund computed the exponential model's variance as $4\zeta(2)-4\zeta(3)+O(n^{-2})$, and Chatterjee proved an order-$n^{-1/2}$ lower bound under tail hypotheses that exclude the bounded uniform law - but no central limit theorem for $C_n$ was known. This paper claims one: $\sqrt{n}\,(C_n-\zeta(2)) \Rightarrow \mathcal{N}(0,\,4\zeta(2)-4\zeta(3))$.

32Significance / 100
1Frontier events
0Verification tasks
0Recorded attempts

Temporal state

Current frontier

No reconciled state yet.

Append-only history

Frontier timeline

probability-statisticsAug 6, 2026Significance 32/100Registry: unreviewed

Central limit theorem for the random assignment problem

Prior state unknownproved

Claims the central limit theorem for the bipartite random assignment problem with bounded uniform costs: $\sqrt{n}\,(C_n-\zeta(2)) \Rightarrow \mathcal{N}(0,\,4\zeta(2)-4\zeta(3))$. The limiting constant is not itself new - Wästlund had computed exactly $4\zeta(2)-4\zeta(3)$ for the mean-one exponential model, and Malatesta, Parisi and Sicuro derived the non-bipartite analogue by replicas - but neither is a proof…

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Research memory

Claims and attempts

Scoped claims

Source authenticated

Let $C_n$ be the minimum cost of a perfect matching in an $n\times n$ matrix of independent uniform random variables. Aldous proved in 1992 that $\mathbb{E}[C_n]$ converges, later identifying the limit as $\zeta(2)$ via the Poisson-weighted infinite tree; Parisi's exact finite-$n$ formula for exponential costs was then proved by Linusson-Wästlund and independently by Nair, Prabhakar and Sharma. The fluctuations resisted. Talagrand applied product-space concentration, Wästlund computed the exponential model's variance as $4\zeta(2)-4\zeta(3)+O(n^{-2})$, and Chatterjee proved an order-$n^{-1/2}$ lower bound under tail hypotheses that exclude the bounded uniform law - but no central limit theorem for $C_n$ was known. This paper claims one: $\sqrt{n}\,(C_n-\zeta(2)) \Rightarrow \mathcal{N}(0,\,4\zeta(2)-4\zeta(3))$.

Claims the central limit theorem for the bipartite random assignment problem with bounded uniform costs: $\sqrt{n}\,(C_n-\zeta(2)) \Rightarrow \mathcal{N}(0,\,4\zeta(2)-4\zeta(3))$. The limiting constant is not itself new - Wästlund had computed exactly $4\zeta(2)-4\zeta(3)$ for the mean-one exponential model, and Malatesta, Parisi and Sicuro derived the non-bipartite analogue by replicas - but neither is a proof for the bounded bipartite model, and Wästlund's zero-free-disk conjecture, which would imply a Gaussian limit, remains open. So the value was expected; the proof of convergence to it is what is claimed. The route is an exact change of variables on an optimal dual potential, after which the residual dependence is a single directed-tree factor whose matrix-tree determinant becomes triangular once the potentials are ordered.

Recorded attempts

Evidence graph

Connected research record

No public relationships recorded yet.