Large deviations of the optimal cost in the random-link matching problem: rigorous rate function, the $\alpha=-2$ singularity, and finite-size corrections

The optimal cost $C_N$ of the random-link matching problem — minimum-weight perfect matching on the complete graph $K_{2N}$ with i.i.d. random link weights — concentrates on $\zeta(2)/2$ with Gaussian fluctuations of variance $(\zeta(2)-\zeta(3))/N$. Malatesta, Parisi and Sicuro (2019) used the replica and cavity methods to derive the full Cramér rate function $L(C)$, equivalently the scaled cumulant generating function $\alpha\Phi(\alpha)$, which is finite only for $\alpha>-2$, diverges as $\alpha\to-2^+$, and fixes the extreme right tail through $\lim_{C\to\infty}L(C)/C=2$. Both derivations are heuristic: they assume the interchange of the replica limits $n\to0$, $\beta\to\infty$ at fixed $n\beta=\alpha$, and the numerical evaluation of the cavity equations loses convergence precisely near the $\alpha=-2$ singularity. The problem is the completion of this fluctuation theory: (i) a rigorous derivation, or controlled convergent computation, of $L(C)$ for all $\alpha$ where the cumulant-generating function is finite; (ii) the behavior in the neighborhood of the $\alpha=-2$ singularity, i.e. the extreme right tail of $L(C)$; (iii) finite-$N$ corrections to the rate function and the higher cumulants beyond the leading variance. Recent work shows major progress on the bipartite assignment analog — exact finite-$n$ rational moment-generating functions with a zero-free-disk conjecture (Wästlund 2026) and a full central limit theorem (Mordant 2026) — but the large-deviation rate function at finite $\alpha$, its singular boundary, and its finite-$N$ structure remain open in both the bipartite and nonbipartite models.

Background

The model. In the random-link matching problem, $2N$ vertices are given, an independent positive random weight $w_{ij}$ with density $\rho$ satisfying $\lim_{w\to0}\rho(w)=1$ is attached to every link $(i,j)$, and one searches for the perfect matching (a set of $N$ edges touching every vertex exactly once) of minimum total weight. The optimal cost is

$$C_N=\min_{M}\sum_{(i,j)\in M}w_{ij},$$

the total cost of the matching: since the matched link weights are of order $1/N$, $C_N$ remains of order one as $N\to\infty$. Its bipartite counterpart is the random assignment problem, in which an $n\times n$ matrix of i.i.d. costs is minimized over all permutations. Replica analyses of the 1980s (historical account in Wästlund 2026) predicted, and later rigorous work confirmed, that $\mathbb{E}C_N\to\zeta(2)/2=\pi^2/12$, where $\zeta$ is the Riemann zeta function; the optimal cost of the assignment problem converges to $\zeta(2)$, i.e. asymptotically twice the optimal matching cost.

Fluctuations. For the matching problem, the source paper (Malatesta, Parisi and Sicuro 2019) computed by replicas the variance

$$\mathbb{E}\bigl[(C_N-\bar C)^2\bigr]=\frac{\zeta(2)-\zeta(3)}{N}+o\Bigl(\frac{1}{N}\Bigr),$$

in agreement with the rigorous variance $(4\zeta(2)-4\zeta(3))/n+o(1/n)$ that Wästlund obtained for the assignment problem with exponential weights (the factor 4 arises because the optimal cost of the assignment problem is asymptotically twice the optimal cost of the matching problem). Small fluctuations are therefore Gaussian to leading order.

Large deviations. The full distribution beyond small fluctuations is described by a large deviation principle $\mathbb{P}(C_N\approx C)\asymp e^{-NL(C)}$ with a Cramér rate function $L$. By the Gärtner–Ellis theorem, when the scaled cumulant generating function (CGF)

$$\alpha\Phi(\alpha)=-\lim_{N\to\infty}\frac{1}{N}\ln\mathbb{E}\bigl[e^{-\alpha N C_N}\bigr]$$

exists and is differentiable and concave in $\alpha$, $L$ is recovered by the Legendre–Fenchel duality $L(C)=\sup_{\alpha}[\alpha\Phi(\alpha)-\alpha C]$, equivalently $\alpha\Phi(\alpha)=\inf_{C}[L(C)+\alpha C]$. The source paper derived $\alpha\Phi(\alpha)$ in two ways: by the replica method — introducing $n$ copies of the system, computing a replicated free energy, and continuing analytically to $n\to0$ at fixed $n\beta=\alpha$, where the inverse temperature $\beta$ is sent to $\infty$; a systematically productive but non-rigorous physics technique — valid for $-2<\alpha<0$; and by the cavity method — iterative equations for cavity fields, messages describing the effective cost shift felt at a vertex when its match is removed, solved on sparse graphs and then taken to the complete graph, justified heuristically by the 'effectively sparse' structure of the dense problem (with high probability a vertex is matched to one of its few cheapest incident links, so the dense graph behaves locally like a sparse one). Numerically, the cavity equations are solved by population dynamics, which represents the cavity-field distribution by a large evolving population of numbers.

What is established and what is not. Both derivations agree and predict that $\alpha\Phi(\alpha)$ is finite only for $\alpha>-2$, diverges as $\alpha\to-2^+$, and — by Legendre duality — that the right tail of the rate function has slope $\lim_{C\to\infty}L(C)/C=2$. However, the replica derivation assumes the interchange of the $n\to0$ and $\beta\to\infty$ limits; the continuation to $\alpha\ge 0$ rests on agreement with the cavity calculation; and near the $\alpha=-2$ singularity the population dynamics fails to converge, while empirical estimation of $\alpha\Phi(\alpha)$ from problem instances requires a number of samples growing exponentially in $N$. In the bipartite assignment model, recent rigorous progress includes exact finite-$n$ moment generating functions — always rational functions, conjectured to have no complex zeros in a disk around the origin, a property that would imply a Gaussian scaling limit — and, for uniformly distributed costs, a full central limit theorem stating that $\sqrt{n}(C_n-\zeta(2))$ converges in distribution to a Gaussian of variance $4\zeta(2)-4\zeta(3)$; none of this reaches the rate function at finite $\alpha$.

Problem Statement

Place the large-deviation theory of the optimal cost of the random-link matching problem on controlled footing, completing the program of Malatesta, Parisi and Sicuro (2019) beyond its heuristic derivation. The three components below are linked parts of one objective — a complete, trustworthy description of the distribution of $C_N$ beyond the Gaussian regime — and the model is kept in its source generality: the complete graph $K_{2N}$ with i.i.d. link weights whose density $\rho$ satisfies $\lim_{w\to0}\rho(w)=1$. Within that objective the components differ in what they establish: a proof of the identification in component 1 fixes $L(C)$ and hence its leading-order content, but it does not by itself establish the behavior of $\alpha\Phi(\alpha)$ near the singularity at $\alpha=-2$ with explicit error control, or the finite-$N$ corrections to the rate function and the higher cumulants beyond the leading-order variance.

1. Rigorous rate function. Prove (or disprove, with the corrected statement) that $C_N$ satisfies a large deviation principle whose rate function $L(C)$ is the Legendre–Fenchel transform of the replica/cavity scaled cumulant generating function $\alpha\Phi(\alpha)$ for every $\alpha$ where the CGF is finite ($\alpha>-2$). This requires justifying — or bypassing with an independent argument — the interchange of the limits $n\to0$ and $\beta\to\infty$ at fixed $n\beta=\alpha$ assumed in the replica derivation, and the equivalence of the replica and cavity derivations, including the continuation from the replica domain $-2<\alpha<0$ to $\alpha\ge 0$. In the disprove case the corrected statement consists of the true rate function $L(C)$ (equivalently the true scaled CGF) together with the range of $\alpha$ on which it holds; the failure of a single sub-step, such as the interchange of the limits $n\to0$ and $\beta\to\infty$ at fixed $n\beta=\alpha$, does not by itself yield that corrected statement.

2. The $\alpha=-2$ singularity and the extreme right tail. Characterize, analytically or by a controlled and convergent numerical scheme with explicit error control, the behavior of $\alpha\Phi(\alpha)$ in a neighborhood of the singularity at $\alpha=-2$, approached from within the domain of validity as $\alpha\to-2^+$ — where population dynamics presently fails to converge and instance sampling requires exponentially many samples — and the corresponding extreme right tail of $L(C)$, in particular the approach to the asymptotic slope $\lim_{C\to+\infty}L(C)/C=2$.

3. Finite-$N$ structure. Quantify the finite-$N$ corrections to the rate function and compute the higher cumulants of $C_N$ beyond the leading-order variance $(\zeta(2)-\zeta(3))/N$.

A rigorous central limit theorem and exact moment generating functions are now known for the bipartite assignment analog; these are related evidence, not a substitute, since the bipartite–nonbipartite correspondence is established at the level of the mean and the variance, and its validity at the level of the full rate function is itself part of what a rigorous treatment must establish.

References

1. E. M. Malatesta, G. Parisi, and G. Sicuro, 'Fluctuations in the random-link matching problem', Physical Review E 100, 032102 (2019). DOI: 10.1103/PhysRevE.100.032102, arXiv:1905.08529. https://doi.org/10.1103/PhysRevE.100.032102
2. J. Wästlund, 'Moment generating functions in combinatorial optimization: Bipartite matching' (2026). arXiv:2602.07563. https://arxiv.org/abs/2602.07563
3. G. Mordant, 'A central limit theorem for the random assignment problem' (2026). arXiv:2608.05123. https://arxiv.org/abs/2608.05123
4. J. Wästlund, 'The mean field traveling salesman and related problems', Acta Mathematica 204, 91–150 (2010). DOI: 10.1007/s11511-010-0046-7. https://doi.org/10.1007/s11511-010-0046-7
5. G. Parisi, G. Perrupato, and G. Sicuro, 'Random-link matching problems on random regular graphs', Journal of Statistical Mechanics (2020) 033301. DOI: 10.1088/1742-5468/ab7127, arXiv:1910.03504. https://doi.org/10.1088/1742-5468/ab7127
6. S. Cao, 'Central limit theorems for combinatorial optimization problems on sparse Erdős–Rényi graphs', Annals of Applied Probability 31(4) (2021). DOI: 10.1214/20-aap1630, arXiv:1905.08366. https://doi.org/10.1214/20-aap1630
7. M. Pastore, A. Di Gioacchino, and P. Rotondo, 'Large deviations of the free energy in the p-spin glass spherical model', Physical Review Research 1, 033116 (2019). DOI: 10.1103/PhysRevResearch.1.033116, arXiv:1909.06196. https://doi.org/10.1103/PhysRevResearch.1.033116
8. B. Lacroix-A-Chez-Toine, Y. V. Fyodorov, and P. Le Doussal, 'Replica-symmetry breaking transitions in the large deviations of the ground-state of a spherical spin-glass', Journal of Statistical Physics 191, 11 (2024). DOI: 10.1007/s10955-024-03232-9, arXiv:2306.11927. https://doi.org/10.1007/s10955-024-03232-9
9. S. Caracciolo, G. Sicuro, and A. Sportiello, 'Spanning trees in the Assignment Problem: two theorems and two conjectures' (2026). arXiv:2608.22308. https://arxiv.org/abs/2608.22308
10. T. Moskalenko, 'On the Properties of the Maximum of a Random Assignment Process' (2025). arXiv:2509.17067. https://arxiv.org/abs/2509.17067