Non-polygonal diagrams, the self-consistent saddle point, and finite-size corrections in the random Euclidean matching problem

The random Euclidean matching problem (EMP) asks for the pairing of N random points on the unit hypercube that minimizes the total cost when each pair's cost is a power p of the points' distance. Lucibello, Parisi and Sicuro (Phys. Rev. E 95, 012302 (2017)) computed its average optimal cost in the replica plus Mayer cluster-expansion framework to one-loop ('polygonal') order via a transfer-matrix resummation, and left precise open problems: (i) the non-polygonal biconnected diagrams (circuit rank at least 2), which they state must be included to obtain the leading contribution to the average optimal cost in low dimensions, were not evaluated analytically or numerically; (ii) the saddle-point equation corrected by the polygonal term could not be iterated to a stable fixed point, so all corrections were evaluated only perturbatively on the mean-field saddle; (iii) the finite-size-correction exponent of the Euclidean cost — analogous to the anomalous $N^{-3/2}$ sub-sub-leading term the same authors derived for the random-link model — remained undetermined. Later work solved the one-dimensional case exactly, made the linearization ansatz rigorous for the bipartite quadratic problem in two dimensions, and developed cavity methods only for random-link and random-regular-graph versions; no later work evaluates the non-polygonal diagrams, the self-consistent saddle, or the Euclidean finite-size exponent. The problem is therefore open. Two further directions posed in the same paper (correlation functions of the optimal matching within this formalism, and a cavity reformulation for the Euclidean problem) are adjacent open problems outside the scope of this problem.

Background

Take N (even) points thrown independently and uniformly on the unit hypercube $[0,1]^d$ , with periodic boundary conditions as in the source setup — the distance $|x_i-x_j|$ is measured between $x_i$ and the nearest image of $x_j$ — and pair them up so as to minimize the total cost $\sum_{(i,j)\in m}|x_i-x_j|^p$ , where $p>0$ is a fixed cost exponent and the sum runs over the $N/2$ pairs of a perfect matching. This is the random Euclidean matching problem (EMP); the disorder-averaged optimal cost $E^*$ is studied through the rescaled quantity $\hat E=\lim_{N\to\infty}N^{p/d-1}E^*$ , which is finite for $p<d$ . If instead the edge costs are independent identically distributed random variables — the random-link model — the problem is exactly solvable by the replica method (the trick of computing an average over the disorder via n copies of the system followed by an $n\to0$ limit; Mézard and Parisi, 1988): the average cost is expressed through a saddle-point function $G(u)$ solving $G(u)=\int\rho(w)e^{-G(w-u)}dw$ , where $\rho$ is the cost distribution; in the standard normalization the random-link optimal cost is $\pi^2/12$ plus finite-N corrections.

The Euclidean problem is harder because the costs of edges sharing endpoints are correlated through the points' positions. Mézard and Parisi (1988) organized the Euclidean corrections to the random-link saddle as a Mayer-type cluster expansion: the replicated action is a sum over biconnected subgraphs $g$ of the complete graph (graphs that stay connected after any single vertex is removed), each weighted by the joint distribution of its edge costs. Houdayer, Boutet de Monvel and Martin (1998) observed numerically that the contribution of a graph class is exponentially small in the dimension $d$ , so the mean-field solution becomes accurate rapidly as $d$ grows, while low dimensions receive large Euclidean corrections. Mézard and Parisi had computed only the first biconnected graph, the triangle. Lucibello, Parisi and Sicuro (2017) completed the next order: in the replica-symmetric saddle-point regime, every biconnected graph of circuit rank $L=1$ (the number of independent cycles; a 'polygon' $p_E$ has $E$ vertices and $E$ edges, $E\ge3$ ) contributes a term $\mathcal{E}_E$ , and the whole polygonal series $\sum_{E\ge3}\mathcal{E}_E$ can be resummed through a replicated transfer matrix, giving $\hat E$ implicitly in terms of the spectra of two integral operators $K$ and $H$ . A delicate feature, when the corrections are expanded around the mean-field saddle $G_{\rm mf}$ , is a vanishing 'mass' at zero momentum: the largest eigenvalue of $H(t,k)$ tends to 1 as the conjugate parameters $t,k\to0$ . Evaluated perturbatively on $G_{\rm mf}$ , the polygonal sum improves on the mean-field prediction for the rescaled cost at $p=1$ , but in low dimensions it still disagrees with the numerical values: in the source's Table I, resummed polygonal values are reported for $d=2,\dots,6$ (e.g. $0.31376$ at $d=2$ , against the numerical value $\hat E=0.3104(2)$ ), while at $d=1$ the full polygonal resummation was not numerically evaluated and the triangular (single-polygon) approximation gives $\approx0.336$ against the simulated $\hat E\approx0.5$ .

What that paper left open defines the present problem. (i) The non-polygonal biconnected diagrams — graphs of circuit rank $L\ge2$ , containing inner loops — were not evaluated, although the authors state they should be included to obtain the leading contribution to the average optimal cost. (ii) The saddle-point equation corrected by the polygonal term could not be iterated to a stable fixed point (numerical instabilities even when truncated to the first polygon), so all corrections were computed perturbatively on $G_{\rm mf}$ , leaving the relevance of the self-consistent saddle $G_{\rm poly}$ unassessed. (iii) In the random-link case, the same authors showed that the large-E decay of the transfer-matrix spectrum, combined with the counting of self-intersections of long polygons at finite N, predicts an anomalous sub-sub-leading finite-size correction of order $N^{-3/2}$ (namely $E^*=\pi^2/12+e_1/N+e_{3/2}/N^{3/2}$ ), and posed the extension of this analysis to the Euclidean problem — the exponent of its finite-size correction — as an open problem. Two further directions posed in the same conclusions — correlation functions of the optimal matching within this diagrammatic formalism, and a cavity (belief-propagation) reformulation of the Euclidean problem — are adjacent open problems rather than part of the present one; for orientation, the two-point correlation function of the bipartite problem is already known at the level of the scaling-hypothesis (linearized Poisson-equation) ansatz (Caracciolo and Sicuro, 2015), and exact one-dimensional results exist (Caracciolo and Sicuro, 2014; Caracciolo, D'Achille and Sicuro, 2017). Much later progress concerns the bipartite Euclidean assignment problem with quadratic cost, where the scaling hypothesis has been made rigorous in two dimensions (Ambrosio, Stra and Trevisan and subsequent work) — a neighboring but distinct problem, since the bipartite cost is dominated by the discrepancy between the two independent point sets, a mechanism absent from the monopartite matching treated here (in which all $N$ points are drawn from a single set and paired among themselves).

Problem Statement

Within the replica plus Mayer cluster-expansion framework set up by Lucibello, Parisi and Sicuro for the random Euclidean (monopartite) matching problem on the unit hypercube with power-law cost $|x_i-x_j|^p$ , complete the evaluation of the average optimal cost beyond polygonal (one-loop) order:

(1) Non-polygonal diagrams. Derive the diagrammatic rules for the biconnected contributions of circuit rank $L\ge2$ (graphs containing inner loops, not reducible to single polygons) and evaluate their total contribution to the rescaled average optimal cost $\hat E(d,p)$ , analytically or numerically with controlled accuracy. Assess whether their inclusion restores quantitative agreement of the theory with the known numerical values in low dimension — in particular $p=1$ , $d=1$ (where simulations give $\hat E\approx0.5$ , the triangular (single-polygon) approximation evaluated in the source gives $\approx0.336$ , and no resummed polygonal value was reported) and $d=2$ (where the resummed polygonal value $\approx0.3138$ remains about $1\%$ above the numerical value $0.3104(2)$ ). The target of this item is the general- $d$ , general- $p$ contribution; the two cases just listed are benchmarks for that assessment, not its exclusive scope.

(2) Self-consistent saddle. Determine the saddle-point function $G_{\rm poly}$ obtained by solving the saddle equation corrected by the polygonal terms — the iteration that was numerically unstable in the source paper — or otherwise control it analytically, and assess how the diagrammatic corrections change when evaluated on the corrected saddle rather than perturbatively on the mean-field saddle $G_{\rm mf}$ .

(3) Finite-size structure. Extend the finite-N analysis that predicts the anomalous $O(N^{-3/2})$ sub-sub-leading correction in the random-link problem (via the large-E asymptotics of the transfer-matrix spectrum and the counting of self-intersections of long polygons at finite N) to the Euclidean matching problem, to obtain a prediction for the exponent of the finite-size correction to the average optimal cost arising from its polygonal contributions.

These three directions were posed as separate open problems in the source paper; all three are required for a complete solution, and they are interrelated: (1) and (2) concern the same cluster expansion in the $N\to\infty$ limit (which diagram classes enter, and at which saddle they are evaluated), and (3) concerns the finite-N structure of the polygonal series of that same expansion. Together they concern the dominant diagrammatic content of the average optimal cost of the Euclidean matching problem in finite dimension and its finite-size scaling. The correlation-function extension and the cavity (belief-propagation) reformulation posed in the same paper's conclusions are adjacent open problems outside the scope of this problem.

References

C. Lucibello, G. Parisi, G. Sicuro, 'One-loop diagrams in the Random Euclidean Matching Problem', Phys. Rev. E 95, 012302 (2017). DOI: 10.1103/PhysRevE.95.012302; arXiv:1609.09310; https://arxiv.org/abs/1609.09310
M. Mézard, G. Parisi, 'The Euclidean matching problem', Journal de Physique 49, 2019 (1988). DOI: 10.1051/jphys:0198800490120201900; https://doi.org/10.1051/jphys:0198800490120201900
J. Houdayer, J. H. Boutet de Monvel, O. C. Martin, 'Comparing mean field and Euclidean matching problems', European Physical Journal B 6, 383 (1998). DOI: 10.1007/s100510050565; https://doi.org/10.1007/s100510050565
S. Caracciolo, C. Lucibello, G. Parisi, G. Sicuro, 'Scaling hypothesis for the Euclidean bipartite matching problem', Phys. Rev. E 90, 012118 (2014). DOI: 10.1103/PhysRevE.90.012118; arXiv:1402.6993; https://arxiv.org/abs/1402.6993
S. Caracciolo, G. Sicuro, 'On the one dimensional Euclidean matching problem: exact solutions, correlation functions and universality', Phys. Rev. E 90, 042112 (2014). DOI: 10.1103/PhysRevE.90.042112; arXiv:1406.7565; https://arxiv.org/abs/1406.7565
S. Caracciolo, G. Sicuro, 'Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions', Phys. Rev. E 91, 062125 (2015). DOI: 10.1103/PhysRevE.91.062125; arXiv:1504.00614; https://arxiv.org/abs/1504.00614
S. Caracciolo, M. D'Achille, G. Sicuro, 'Random Euclidean matching problems in one dimension', Phys. Rev. E 96, 042102 (2017). DOI: 10.1103/PhysRevE.96.042102; arXiv:1707.05541; https://arxiv.org/abs/1707.05541
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
S. Caracciolo, M. D'Achille, G. Sicuro, 'Anomalous scaling of the optimal cost in the one-dimensional random assignment problem', Journal of Statistical Physics 174, 846-864 (2018). DOI: 10.1007/s10955-018-2212-9; arXiv:1803.04723; https://arxiv.org/abs/1803.04723
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
G. Parisi, G. Perrupato, G. Sicuro, 'Random-link matching problems on random regular graphs', Journal of Statistical Mechanics 2020, 033301 (2020). DOI: 10.1088/1742-5468/ab7127; arXiv:1910.03504; https://arxiv.org/abs/1910.03504
D. Benedetto, E. Caglioti, S. Caracciolo, M. D'Achille, G. Sicuro, A. Sportiello, 'Random assignment problems on 2d manifolds', Journal of Statistical Physics (2021). DOI: 10.1007/s10955-021-02768-4; arXiv:2008.01462; https://arxiv.org/abs/2008.01462
L. Ambrosio, F. Stra, D. Trevisan, 'A PDE approach to a 2-dimensional matching problem', arXiv:1611.04960 (2016). https://arxiv.org/abs/1611.04960
L. Ambrosio, F. Glaudo, D. Trevisan, 'On the optimal map in the 2-dimensional random matching problem', arXiv:1903.12153 (2019). https://arxiv.org/abs/1903.12153
L. Ambrosio, M. Goldman, D. Trevisan, 'On the quadratic random matching problem in two-dimensional domains', arXiv:2110.14372 (2021). https://arxiv.org/abs/2110.14372
M. Goldman, D. Trevisan, 'Convergence of asymptotic costs for random Euclidean matching problems', arXiv:2009.04128 (2020). https://arxiv.org/abs/2009.04128
D. Benedetto, E. Caglioti, 'Euclidean random matching in 2D for non-constant densities', arXiv:1911.10523 (2019). https://arxiv.org/abs/1911.10523
N. Clozeau, F. Mattesini, 'Annealed quantitative estimates for the quadratic 2D-discrete random matching problem', arXiv:2303.00353 (2023). https://arxiv.org/abs/2303.00353
E. Caglioti, F. Pieroni, 'Random matching in 2D with exponent 2 for gaussian densities', arXiv:2302.02602 (2023). https://arxiv.org/abs/2302.02602
S. Caracciolo, R. Fabbricatore, M. Gherardi, R. Marino, G. Parisi, G. Sicuro, 'Criticality and conformality in the random dimer model', Phys. Rev. E 103, 042127 (2021). DOI: 10.1103/PhysRevE.103.042127; arXiv:2012.13956; https://arxiv.org/abs/2012.13956
S. Caracciolo, G. Sicuro, A. Sportiello, 'Spanning trees in the Assignment Problem: two theorems and two conjectures', arXiv:2608.22308 (2026). https://arxiv.org/abs/2608.22308
M. D'Achille, F. Mattesini, D. Trevisan, 'Concentration for random Euclidean combinatorial optimization', arXiv:2602.21851 (2026). https://arxiv.org/abs/2602.21851
A. Di Gioacchino, 'Euclidean correlations in Combinatorial Optimization Problems: a Statistical Physics Approach', PhD thesis, Università degli Studi di Milano (2019). arXiv:2001.03249; https://arxiv.org/abs/2001.03249
E. M. Malatesta, 'Random Combinatorial Optimization Problems: Mean Field and Finite-Dimensional Results', PhD thesis, Sapienza Università di Roma (2018). arXiv:1902.00455; https://arxiv.org/abs/1902.00455
M. D'Achille, 'Statistical properties of the Euclidean random assignment problem' (Proprietés statistiques du problème de l'assignation aléatoire euclidienne), PhD thesis, Université Paris-Saclay (2021). DOI: 10.70675/b6ac9ea7z133bz4255z8bf8z806ca0d1683b; https://doi.org/10.70675/b6ac9ea7z133bz4255z8bf8z806ca0d1683b