In the random assignment problem on the complete bipartite graph KN,NK_{N,N}, where the N×NN\times N cost matrix has independent, identically distributed entries whose density behaves as wrw^r near the origin, the rescaled average optimal cost admits a finite-NN expansion containing non-analytic terms of order N−k/(r+1)N^{-k/(r+1)}, 1≤k≤⌊r⌋+11\le k\le\lfloor r\rfloor+1. Caracciolo, D'Achille, Malatesta and Sicuro (Phys. Rev. E 95, 052129 (2017)) computed in closed form only the first non-analytic correction (k=1k=1, proportional to the coefficient η1\eta_1 of the weight density's Maclaurin expansion) and two analytic O(1/N)O(1/N) terms. The coefficients Δφr(k)\Delta\varphi_r^{(k)} of the higher non-analytic corrections, 2≤k≤⌊r⌋+12\le k\le\lfloor r\rfloor+1, remain uncomputed, and so does their resummation in the regime r→∞r\to\infty at fixed NN, where these corrections become of the same order as the leading term and the r→∞r\to\infty and N→∞N\to\infty limits fail to commute.

Background

The random assignment problem asks for the minimum-cost perfect matching (a bijection pairing each element of one set with exactly one element of the other) between two sets of NN elements when the N2N^2 matching costs are independent identically distributed random variables; it is a mean-field model of combinatorial optimization solved with the replica method (an analytic continuation n→0n\to0 of the number of copies of the system) and, rigorously, with probabilistic techniques. For weights with a density positive at the origin (the case r=0r=0, e.g. exponential or uniform weights), the average optimal cost converges to ζ(2)=π2/6\zeta(2)=\pi^2/6 (Aldous, 2001), and the full finite-NN expectation is known exactly: Parisi conjectured E[CN]=∑k=1N1/k2\mathrm{E}[C_N]=\sum_{k=1}^N 1/k^2 for mean-one exponential weights, proved by Linusson and Wästlund (journal version 2004) and by Nair, Prabhakar and Sharma (2003). The replica finite-size corrections for r=0r=0 were derived by Mézard and Parisi (1987) and corrected by Parisi and Ratiéville (2002). These complete-graph mean-field results also serve as the baseline against which finite-dimensional (Euclidean) matching problems are compared (Houdayer, Boutet de Monvel and Martin, 1998).

Caracciolo, D'Achille, Malatesta and Sicuro (2017) generalized the finite-size analysis to weight densities of the form ρr(w)=wr∑k≥0ηk(r)wk\rho_r(w)=w^r\sum_{k\ge0}\eta_k(r)w^k near the origin, with r>−1r>-1 and η0≠0\eta_0\ne0; the two canonical families are the pure power law ρrP(w)=(r+1)wr\rho_r^P(w)=(r+1)w^r on [0,1][0,1] (all ηk=0\eta_k=0 for k≥1k\ge1) and the Gamma law ρrΓ(w)∝wre−w\rho_r^\Gamma(w)\propto w^re^{-w} (all ηk≠0\eta_k\ne0). The average optimal cost scales as Nr/(r+1)N^{r/(r+1)}, and its rescaled value E^r(N)=N−r/(r+1)E[CN]\hat E_r(N)=N^{-r/(r+1)}\mathrm{E}[C_N] is governed by a saddle-point function G^r\hat G_r solving the integral equation G^r(l)=∫−l∞(l+y)re−G^r(y) dy/Γ(r+1)\hat G_r(l)=\int_{-l}^\infty(l+y)^re^{-\hat G_r(y)}\,dy/\Gamma(r+1), which is known in closed form only for r=0r=0 and, after rescaling, for r→∞r\to\infty. Their main result is the finite-size expansion

E^r(N)=E^r+∑k=1⌊r⌋+1ΔF^r(k)+ΔF^rT+ΔF^rF+o(1/N),\hat E_r(N)=\hat E_r+\sum_{k=1}^{\lfloor r\rfloor+1}\Delta\hat F_r^{(k)}+\Delta\hat F_r^T+\Delta\hat F_r^F+o(1/N),

where ΔF^r(k)=Δφr(k)/Nk/(r+1)\Delta\hat F_r^{(k)}=\Delta\varphi_r^{(k)}/N^{k/(r+1)} are non-analytic corrections (generically non-integer powers of 1/N1/N) proportional to the low-order coefficients ηk\eta_k, while ΔF^rT\Delta\hat F_r^T (from the subleading ΔST\Delta S_T term of the replicated action, generated when the Gaussian integrals over the replicated fields are re-exponentiated and evaluated at the saddle point) and ΔF^rF\Delta\hat F_r^F (from the Gaussian fluctuations around the saddle point, a ln⁡det⁡\ln\det of the Hessian contribution) are analytic O(1/N)O(1/N) terms. Closed forms were obtained only for Δφr(1)\Delta\varphi_r^{(1)}, ΔF^rT\Delta\hat F_r^T and ΔF^rF\Delta\hat F_r^F; the higher coefficients Δφr(k)\Delta\varphi_r^{(k)}, 2≤k≤⌊r⌋+12\le k\le\lfloor r\rfloor+1, were left unevaluated.

These missing terms are not a small refinement: for the pure power-law family all non-analytic corrections vanish and the limits r→∞r\to\infty and N→∞N\to\infty commute, but for any family with nonzero higher ηk\eta_k — such as the mean-rescaled Gamma law ρrγ(w)=(r+1)r+1Γ(r+1)wre−(r+1)w\rho_r^\gamma(w)=\frac{(r+1)^{r+1}}{\Gamma(r+1)}w^re^{-(r+1)w}, the unit-mean rescaling of ρrΓ\rho_r^\Gamma that converges weakly to δ(w−1)\delta(w-1) as r→∞r\to\infty — the limits do not commute. In the r→∞r\to\infty limit at fixed NN every ΔF^r(k)\Delta\hat F_r^{(k)} contributes at leading order, so the corrections must be summed to obtain the correct fixed-NN cost of the limiting problem. For ρrγ\rho_r^\gamma the known pieces give E^=1/e+1/e2+⋯\hat E=1/e+1/e^2+\cdots, where the leading value is E^∞=1/e\hat E_\infty=1/e, the first correction is ΔF^∞(1)=1/e2\Delta\hat F_\infty^{(1)}=1/e^2, and the whole correction series must sum to 1−1/e1-1/e; the uncomputed terms with k≥2k\ge2 therefore contribute more, in total, than the one term that is known. Numerically, extracting even the first two amplitudes from data is ill-conditioned for r≳1r\gtrsim1 because the exponents 1/(r+1)1/(r+1) and 2/(r+1)2/(r+1) are close.

Problem Statement

For the random assignment problem on KN,NK_{N,N} with independent costs whose density is ρr(w)=wr∑k≥0ηk(r)wk\rho_r(w)=w^r\sum_{k\ge0}\eta_k(r)w^k near the origin (r>−1r>-1, η0≠0\eta_0\ne0), compute in closed form, for general r≥1r\ge1, the coefficients Δφr(k)\Delta\varphi_r^{(k)} of the non-analytic finite-size corrections ΔF^r(k)=Δφr(k)N−k/(r+1)\Delta\hat F_r^{(k)}=\Delta\varphi_r^{(k)}N^{-k/(r+1)} of the rescaled average optimal cost, for every 2≤k≤⌊r⌋+12\le k\le\lfloor r\rfloor+1, as explicit functionals of rr, the low-order coefficients ηj\eta_j (j≤kj\le k), and the saddle-point function G^r\hat G_r (the solution of the integral equation above) — completing the finite-size expansion whose k=1k=1 and analytic terms are already known. The required result is the closed-form coefficients Δφr(k)\Delta\varphi_r^{(k)} for every 2≤k≤⌊r⌋+12\le k\le\lfloor r\rfloor+1; the large-rr behaviour of the resulting series is the motivation for computing them rather than a separate requirement, and the quoted limiting total serves only as a consistency check on the coefficients. These coefficients also govern the r→∞r\to\infty limit at fixed NN, which for weight families with nonzero higher ηk\eta_k does not commute with the N→∞N\to\infty limit: in that regime all these finite-size corrections are expected to contribute to the leading term. For the mean-rescaled Gamma law ρrγ(w)=(r+1)r+1Γ(r+1)wre−(r+1)w\rho_r^\gamma(w)=\frac{(r+1)^{r+1}}{\Gamma(r+1)}w^re^{-(r+1)w}, the known terms give the series E^=1/e+1/e2+⋯\hat E=1/e+1/e^2+\cdots, which is known to sum to the fixed-NN cost 11 of the limiting δ(w−1)\delta(w-1) weights, so the missing k≥2k\ge2 coefficients directly enter this noncommuting large-rr regime.

References

  1. S. Caracciolo, M. P. D'Achille, E. M. Malatesta, G. Sicuro, "Finite-size corrections in the random assignment problem", Phys. Rev. E 95, 052129 (2017), DOI: 10.1103/PhysRevE.95.052129, arXiv:1702.05991, https://arxiv.org/abs/1702.05991
  2. M. Mézard, G. Parisi, "On the solution of the random link matching problems", J. Phys. (France) 48, 1451-1459 (1987), DOI: 10.1051/jphys:019870048090145100, https://doi.org/10.1051/jphys:019870048090145100
  3. G. Parisi, M. Ratiéville, "On the finite size corrections to some random matching problems", Eur. Phys. J. B 29, 457-468 (2002), DOI: 10.1140/epjb/e2002-00326-3, https://doi.org/10.1140/epjb/e2002-00326-3
  4. G. Parisi, M. Ratiéville, "Neighborhood preferences in random matching problems", Eur. Phys. J. B 22, 229-237 (2001), DOI: 10.1007/pl00011144, https://doi.org/10.1007/pl00011144
  5. J. Houdayer, J. H. Boutet de Monvel, O. C. Martin, "Comparing mean field and Euclidean matching problems", Eur. Phys. J. B 6, 383-393 (1998), DOI: 10.1007/s100510050565, https://doi.org/10.1007/s100510050565
  6. G. Parisi, "A conjecture on random bipartite matching", arXiv:cond-mat/9801176 (1998), https://arxiv.org/abs/cond-mat/9801176
  7. D. J. Aldous, "The zeta(2) limit in the random assignment problem", Random Struct. Algor. 18, 381-418 (2001), DOI: 10.1002/rsa.1015, arXiv:math/0010063, https://arxiv.org/abs/math/0010063
  8. S. Linusson, J. Wästlund, "A proof of Parisi's conjecture on the random assignment problem", Probab. Theory Relat. Fields 128, 419-440 (2004), DOI: 10.1007/s00440-003-0308-9, arXiv:math/0303214, https://arxiv.org/abs/math/0303214
  9. C. Nair, B. Prabhakar, M. Sharma, "Proofs of the Parisi and Coppersmith-Sorkin conjectures for the finite random assignment problem", Proc. 44th IEEE Symposium on Foundations of Computer Science (FOCS 2003), pp. 168-178, DOI: 10.1109/SFCS.2003.1238191, https://doi.org/10.1109/SFCS.2003.1238191
  10. E. M. Malatesta, "Random combinatorial optimization problems: mean field and finite-dimensional results", PhD thesis, Università degli Studi di Milano (defended 21 December 2018), DOI: 10.13130/MALATESTA-ENRICO-MARIA_PHD2018-12-21, arXiv:1902.00455, https://arxiv.org/abs/1902.00455
  11. E. M. Malatesta, G. Parisi, G. Sicuro, "Fluctuations in the random-link matching problem", Phys. Rev. E 100, 032102 (2019), DOI: 10.1103/PhysRevE.100.032102, arXiv:1905.08529, https://arxiv.org/abs/1905.08529
  12. G. Parisi, G. Perrupato, G. Sicuro, "Random-link matching problems on random regular graphs", J. Stat. Mech. (2020) 033301, DOI: 10.1088/1742-5468/ab7127, arXiv:1910.03504, https://arxiv.org/abs/1910.03504
  13. S. Caracciolo, A. K. Hartmann, S. Kirkpatrick, M. Weigel, "Simulated annealing, optimization, searching for ground states", Chapter 1, pp. 1-20, in "Spin Glass Theory and Far Beyond" (World Scientific, 2023), DOI: 10.1142/9789811273926_0001, arXiv:2301.00683, https://arxiv.org/abs/2301.00683
  14. G. Mordant, "A central limit theorem for the random assignment problem", arXiv:2608.05123 (2026), https://arxiv.org/abs/2608.05123