Completing the cycle-expansion theory of finite-size corrections for random-link matching problems on random regular graphs

The random-link matching problem — finding a maximum-cardinality matching of minimum total weight on a graph whose edges carry independent random weights — is exactly solved on the complete graph, where the average optimal cost converges to $\zeta(2)/2$ with a finite-size expansion whose $1/N$ term is a sum of odd-cycle contributions plus an anomalous $N^{-3/2}$ correction. Parisi, Perrupato and Sicuro (J. Stat. Mech. 2020) extended the analysis to random $z$-regular graphs via the cavity method, deriving the asymptotic average optimal cost and an ansatz for the $1/N$ finite-size correction as a possible cycle-independent constant plus contributions of individual cycles weighted by their Poisson multiplicities, verified term by term against simulations. Their analysis left open two specific issues: the large-length decay law of the even-cycle contributions at fixed coordination, and the possible non-zero cycle-independent constant for weight distributions other than the exponential one. The problem remains open.

Background

In the random-link matching problem (MP), each edge $e$ of a graph $G=(V,E)$ carries an independent random weight $w_e\geq 0$, and one searches for the matching — a set of edges with no vertices in common — of maximum cardinality having minimum total cost. On the complete graph $K_N$ (every pair of vertices joined by an edge) with exponentially distributed weights, this is a classic disordered combinatorial optimization problem, solved exactly by replica (a formal averaging-over-disorder-copies technique from spin-glass theory) and cavity computations: the average optimal cost (AOC) satisfies $\lim_{N\to\infty}E_{K_N}=\zeta(2)/2$ (with $\zeta$ the Riemann zeta function), and the finite-size corrections are known in detail — a $1/N$ term given by a universal sum of odd contributions $I_{2k+1}$ (explicit one-dimensional integrals) plus an anomalous $N^{-3/2}$ term, whose origin was traced to the cut-off of the sum over cycle lengths at lengths of order $\sqrt{N}$ (Parisi and Ratiéville 2002; Lucibello, Parisi and Sicuro 2017; Lucibello, Malatesta, Parisi and Sicuro 2018). In the relaxed fractional matching problem (FMP) the edge occupancies may take any value in $[0,1]$, and in the loopy fractional matching problem (LMP) a vertex may additionally 'self-match' at a price; on the complete graph these variants isolate which finite-size terms come from cycles of the graph.

Sparse random graphs generalize this setting. A random $z$-regular graph $G(N,z)$ is drawn uniformly among graphs in which every one of $N$ vertices has exactly $z$ neighbors; such graphs are locally tree-like, meaning that a bounded-radius neighborhood coincides with the infinite $z$-regular tree (the Bethe lattice) with high probability as $N\to\infty$. The cavity method (a message-passing technique from spin-glass theory) exploits this: optimization on a tree decouples into recursive one-point equations for 'cavity fields' $h$, whose probability distribution satisfies a self-consistent distributional equation, solved numerically by population dynamics, in which the field distribution is represented by a large finite pool of samples iteratively updated through the same equation. Closed cycles, which cannot occur on a tree, are rare: the number of cycles of length $\ell$ in a large random $z$-regular graph is asymptotically Poisson with mean $\bar{n}_\ell(z)=(z-1)^\ell/(2\ell)$, so there are only $O(1)$ short cycles in the whole graph.

Parisi, Perrupato and Sicuro (2020) computed the AOC $E_z$ of the MP, FMP and LMP on $G(N,z)$ for exponential weights with density $\rho_z(w)=\frac{2}{z}e^{-2w/z}\theta(w)$ (with $\theta$ the step function), finding $E_z\to\zeta(2)/2$ as $z\to\infty$, and proposed for the MP the finite-size expansion

$$E_z(N) = E_z + \frac{E_z^{(1)}}{N} + \frac{E_z^{(3/2)}}{N^{3/2}}+\cdots,\qquad E_z^{(1)} = \upsilon_z + \sum_{\ell\geq 3}\bar{n}_\ell(z)\,\varphi_\ell(z),$$

where $\varphi_\ell(z)$ is the cost contribution of a single $\ell$-cycle embedded in the infinite tree (computed again by the cavity method, as a free-energy difference between the graph containing the cycle and the pure tree) and $\upsilon_z$ is a cycle-independent constant. This cycle expansion was verified against numerical simulations both globally and term by term. Odd- and even-cycle terms behave very differently: odd terms are positive and, at fixed $z$, scale as $\ell^{-2}$ at large $\ell$, which — combined with the cut-off $\ell\lesssim\sqrt{N}$ of realizable cycle lengths in a finite graph — generates the anomalous $N^{-3/2}$ correction; even terms are negative, much smaller, and decay so fast in $\ell$ and $z$ that their asymptotics could not be extracted numerically. For $\ell=3$ and $\ell=5$ the odd terms converge, as $z\to\infty$, to the corresponding odd terms of the complete-graph finite-size expansion — the 'sparse-to-dense correspondence' — numerically supporting the older conjecture that the complete-graph $1/N$ corrections are cycle contributions.

Two rigorous neighbors frame what is proven. For unweighted matchings, Bordenave, Lelarge and Salez (2013) proved the cavity predictions for matching statistics on infinite locally tree-like graphs. For spin systems on random factor graphs (bipartite graphs coupling variable nodes to local constraint nodes) — but not for weighted matching — Coja-Oghlan, Efthymiou, Jaafari, Kang and Kapetanopoulos (2018) rigorously grounded the cavity method, proving in particular that the finite-size corrections to the leading-order free energy decompose into a sum of cycle contributions; the analogous justification for the matching problem is absent. Finally, for disordered spin systems on Erdős–Rényi random graphs — in which the degree of each vertex fluctuates around its mean, unlike in regular graphs — Ferrari, Lucibello, Morone, Parisi, Ricci-Tersenghi and Rizzo (2013) showed that the finite-size expansion acquires extra contributions from chain-like topological structures created by degree fluctuations; the source notes that such chain contributions are absent on random regular graphs, where the vertex connectivity does not fluctuate, and no analogous analysis exists for matching.

Problem Statement

Complete the cycle-expansion theory of finite-size corrections for random-link matching problems on sparse random graphs initiated by Parisi, Perrupato and Sicuro (2020), by resolving the two issues their analysis explicitly left open. Both concern the same object — the cycle expansion $E_z^{(1)}=\upsilon_z+\sum_{\ell\geq 3}\bar{n}_\ell(z)\varphi_\ell(z)$ for the $1/N$ correction of the average optimal cost on random $z$-regular graphs and its large-$\ell$ structure — and together they would turn a numerically verified ansatz into a complete, well-founded theory.

(1) Even-cycle asymptotics: determine the decay of the even-cycle contributions $\bar{n}_{2k}(z)\varphi_{2k}(z)$ (equivalently, since the multiplicity $\bar{n}_\ell(z)$ is explicit, of $\varphi_{2k}(z)$) as $k\to\infty$ at fixed $z$ — in particular whether the decay is faster than algebraic in $k$, and with what law; the source analysis could not extract it because the terms are too small for population-dynamics numerics, and its note on the assignment problem suggests $\bar{n}_\ell\varphi_\ell\sim\ell^{-\alpha}$ with $\alpha\geq 3$, or faster, a fact that needs a more accurate investigation.

(2) Cycle-independent constant: determine whether a non-zero $\upsilon_z$ can occur for weight distributions other than the exponential one used in the source (for which it appears negligible), and if so for which distributions and with what value; on the complete graph such constants are known to depend on the weight distribution.

References

1. Giorgio Parisi, Gianmarco Perrupato, Gabriele Sicuro, "Random-link matching problems on random regular graphs", Journal of Statistical Mechanics: Theory and Experiment 2020, 033301 (2020). DOI: 10.1088/1742-5468/ab7127. https://doi.org/10.1088/1742-5468/ab7127 (arXiv:1910.03504, https://arxiv.org/abs/1910.03504)
2. Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, Tobias Kapetanopoulos, "Charting the Replica Symmetric Phase", Communications in Mathematical Physics 359, 603–698 (2018). DOI: 10.1007/s00220-018-3096-x. https://doi.org/10.1007/s00220-018-3096-x
3. Carlo Lucibello, Giorgio Parisi, Gabriele Sicuro, "One-loop diagrams in the random Euclidean matching problem", Physical Review E 95, 012302 (2017). DOI: 10.1103/PhysRevE.95.012302. https://doi.org/10.1103/PhysRevE.95.012302
4. Carlo Lucibello, Enrico M. Malatesta, Giorgio Parisi, Gabriele Sicuro, "The random fractional matching problem", Journal of Statistical Mechanics: Theory and Experiment 2018, 053301 (2018). DOI: 10.1088/1742-5468/aabbc8. https://doi.org/10.1088/1742-5468/aabbc8
5. G. Parisi, M. Ratiéville, "On the finite size corrections to some random matching problems", The European Physical Journal B 29, 457–468 (2002). DOI: 10.1140/epjb/e2002-00326-3. https://doi.org/10.1140/epjb/e2002-00326-3
6. Charles Bordenave, Marc Lelarge, Justin Salez, "Matchings on infinite graphs", Probability Theory and Related Fields 157, 183–208 (2013). DOI: 10.1007/s00440-012-0453-0. https://doi.org/10.1007/s00440-012-0453-0
7. U. Ferrari, C. Lucibello, F. Morone, G. Parisi, F. Ricci-Tersenghi, T. Rizzo, "Finite-size corrections to disordered systems on Erdös-Rényi random graphs", Physical Review B 88, 184201 (2013). DOI: 10.1103/PhysRevB.88.184201. https://doi.org/10.1103/PhysRevB.88.184201
8. Guilhem Semerjian, Gabriele Sicuro, Lenka Zdeborová, "Recovery thresholds in the sparse planted matching problem", Physical Review E 102, 022304 (2020). DOI: 10.1103/PhysRevE.102.022304. https://doi.org/10.1103/PhysRevE.102.022304
9. Gianmarco Perrupato, Tommaso Rizzo, "Thermodynamics of the Fredrickson-Andersen model on the Bethe lattice", Physical Review E 110, 044312 (2024). DOI: 10.1103/PhysRevE.110.044312. https://doi.org/10.1103/PhysRevE.110.044312 (arXiv:2312.01430)
10. Gianmarco Perrupato, Maria Chiara Angelini, Giorgio Parisi, Federico Ricci-Tersenghi, Tommaso Rizzo, "Ising spin glass on random graphs at zero temperature: Not all spins are glassy in the glassy phase", Physical Review B 106, 174202 (2022). DOI: 10.1103/PhysRevB.106.174202. https://doi.org/10.1103/PhysRevB.106.174202
11. S. Caracciolo, R. Fabbricatore, M. Gherardi, R. Marino, G. Parisi, G. Sicuro, "Criticality and conformality in the random dimer model", Physical Review E 103, 042127 (2021). DOI: 10.1103/PhysRevE.103.042127. https://doi.org/10.1103/PhysRevE.103.042127
12. C. D. Rodríguez-Camargo, E. A. Mojica-Nava, N. F. Svaiter, "Sherrington-Kirkpatrick model for spin glasses: Solution via the distributional zeta function method", Physical Review E 104, 034102 (2021). DOI: 10.1103/PhysRevE.104.034102. https://doi.org/10.1103/PhysRevE.104.034102
13. Nathanaël Enriquez, Mike Liu, Laurent Ménard, Vianney Perchet, "Optimal Unimodular Matching", arXiv:2407.03141 (2024; v2 revised March 2025). https://arxiv.org/abs/2407.03141