The Euclidean matching problem beyond the triangular-correlation level: higher-order connected link correlations, the exact finite-dimensional optimal cost, and extensions to other Euclidean optimization problems

The Euclidean matching problem asks for the minimum-total-cost perfect matching of $2N$ points placed at random in the unit hypercube of $\mathbb{R}^d$ , with link costs given by a power $\nu$ of the Euclidean distance. In 1988 Mézard and Parisi computed its typical optimal cost by combining the exactly solved random-link model, in which all pairwise costs are independent random variables, with the leading Euclidean correction: the connected three-link correlation of distances that close a triangle. They explicitly set aside higher-order connected link correlations, which they noted could be included "at the price of having to solve more and more complex saddle point equations", deferred a comparison with numerical simulations to later work, and proposed extending the same correlation-based improvement scheme to the travelling salesman problem and to finite-dimensional spin glasses. The deferred numerical comparison was performed by Boutet de Monvel and Martin (1997) and by Houdayer, Boutet de Monvel and Martin (1998): random-link theory errs by about 4% at $d=2$ and triangular correlations reduce the error to roughly 0.4%, but the same authors argued that no fixed-order $k$ -link correlation expansion can reproduce the Euclidean energy density, whose dimensional dependence is beyond all orders in $k$ . Lucibello, Parisi and Sicuro (2017) then summed all one-loop polygonal corrections, going beyond the triangle, and explicitly left two-loop and higher diagrams, the self-consistent correlated saddle point, and correlation functions open. Exact typical-cost results are known only for the bipartite version of the problem and in one dimension. The surviving open core is a controlled analytic theory of the monopartite Euclidean matching problem in $d\ge2$ beyond the one-loop level — including the exact rescaled optimal-cost constant and its $1/d$ expansion; the extension of the correlation-based scheme to the Euclidean travelling salesman problem and to finite-dimensional spin-glass models is a separate generalization explicitly proposed by the source.

Background

Minimum-weight perfect matching is one of the canonical combinatorial-optimization problems: given $2N$ points and a cost for every pair, choose $N$ disjoint pairs covering all the points so that the total cost is minimal. Unlike the travelling salesman problem (TSP), which asks for the shortest closed tour visiting every point exactly once, a minimum matching can be computed in polynomial time, which makes matching a clean testing ground for statistical-mechanical theories of typical — that is, instance-averaged — optima of disordered systems.

In the statistical-mechanics approach one studies the average optimal cost over a random ensemble of instances. The main analytic tool is the replica method, a formal procedure in which an average of a logarithm is exchanged for the analysis of $n$ identical copies of the system followed by the analytic continuation $n\to0$ , usually within the replica-symmetric (RS) ansatz, which assumes that the copies remain statistically equivalent. Mézard and Parisi solved the random-link version of the matching problem by this method (1985, 1987): all pairwise costs $\ell_{ij}$ are taken to be independent identically distributed random variables whose common density behaves near zero as $\rho(\ell)\sim\ell^{r}$ , and the average optimal cost follows from a self-consistent saddle-point equation — an integral equation, for an order parameter $G(x)$ , fixed by the cost distribution alone. The same replica formalism was originally developed for spin glasses — disordered magnetic systems whose random, frustrated interactions cannot all be satisfied simultaneously; their exactly solved infinite-range prototype is the Sherrington-Kirkpatrick (SK) model, while genuinely finite-dimensional spin glasses remain only partially understood.

The Euclidean version, the subject of the 1988 source paper, replaces the independent costs by genuine geometric ones: $2N$ points placed independently and uniformly in the unit hypercube of $\mathbb{R}^d$ , with costs $\ell_{ij}=|\mathbf{x}_i-\mathbf{x}_j|^{\nu}$ (the " $\nu$ -Euclidean" matching problem; $\nu=1$ is the usual total length). Since the optimal matching uses only short links, of cost of order $N^{-\nu/d}$ , the total optimal cost scales as $N^{1-\nu/d}$ times a dimensionless constant, and the random-link model with the matched short-distance exponent $r=d/\nu-1$ is a natural mean-field approximant. Mézard and Parisi showed that, after a rescaling of lengths, the Euclidean problem converges to the random-link one when $d,\nu\to\infty$ at fixed $d/\nu$ , so the discrepancy at finite dimension is precisely the object of interest.

The geometric costs are not independent: they are strongly constrained by the triangle inequalities among nearby points. Mézard and Parisi quantified this through connected link averages — cumulants of the joint statistics of the links used by the optimal matching. The connected two-link average vanishes, but the connected three-link average is nonzero precisely when the three links close a triangle (it scales as $1/N^2$ , still contributing an extensive amount, since two short links force the third to be short). Keeping only this triangular correlation inside a replica-symmetric computation modifies the saddle-point equation, and its numerical solution gives corrections of a few percent to the random-link result.

In the modern reformulation (Lucibello, Parisi and Sicuro, 2017) these corrections are organized by a Mayer cluster expansion — the standard graphical expansion of the thermodynamics of interacting particles into labeled graphs — in which the mean-field action of the random-link model is corrected graph by graph. The one-loop terms are the polygonal diagrams $p_E$ with $E$ vertices and $E$ edges ( $p_3$ being the triangle of the 1988 paper); diagrams of two-loop order and higher contain additional internal loops and encode the connected correlations of four or more short links.

What is exactly known in the neighborhood: for the bipartite (assignment) version of the problem — two independent sets of points, matched red-to-blue rather than within a single set — Caracciolo, Lucibello, Parisi and Sicuro (2014) proposed a scaling ansatz based on a linearized Poisson equation that gives the exact asymptotic average cost for quadratic costs in $d=1,2$ and the exact subleading exponent in higher dimensions; this ansatz was later proven to capture also the optimal transport map — the cost-minimizing rearrangement of one point set onto the other — in two dimensions (Ambrosio, Glaudo and Trevisan, 2019) and for the leading order of several bipartite problems in $d\ge3$ (Goldman and Trevisan, 2023), with the exact two-dimensional constant for Gaussian densities computed by Caglioti and Pieroni (2024). In one dimension, both the monopartite and the bipartite matching problems have been solved exactly (Caracciolo, D'Achille and Sicuro, 2017). None of these results covers the monopartite Euclidean problem — matching within a single point set, the case of the 1988 paper — in dimension $d\ge2$ , which remains described only by the random-link solution plus perturbative correlation corrections.

Problem Statement

For the monopartite Euclidean matching problem in dimension $d\ge2$ with cost exponent $\nu$ (the 1988 convention, understood in the short-link regime $0<\nu<d$ in which the optimal cost obeys the scaling of item 2 below; linear costs $\nu=1$ being the case for which published benchmark numerics exist), the task is:

Give a controlled analytic treatment of the average optimal cost beyond the one-loop level, where "controlled" means accompanied by quantified error bounds or an established convergence or asymptotic status. Beyond the polygonal one-loop corrections are the two-loop and higher cluster corrections — diagrams with additional inner loops, encoding the connected statistics of four or more short links. The 1998 argument that any fixed-order $k$ -link truncation misses the $O(1/d^2)$ term of the $1/d$ expansion shows that the dimensional dependence is beyond all orders in $k$ . Whether the self-consistent correlated saddle-point equations admit a solution, and whether the replica-symmetric ansatz is exact for the Euclidean ensemble, are related open subproblems.
Determine analytically, exactly or with controlled error bounds, the rescaled asymptotic constant of the average optimal cost $\bar{L}_{d,\nu}(N)\sim N^{1-\nu/d}\,\ell_{d,\nu}$ at fixed finite $d\ge2$ and $0<\nu<d$ (the cases for which published benchmark numerics exist: $\nu=1$ and $2\le d\le10$ ), and in particular the coefficient of the $1/d^2$ term of its large- $d$ expansion — a coefficient that fixed-order $k$ -link truncation does not capture.
Extend the correlation-based improvement scheme itself to the other finite-dimensional optimization problems named in the source: the Euclidean travelling salesman problem (whose random-link version was solved in 1986) and finite-dimensional spin glasses, where the Sherrington-Kirkpatrick mean-field model would play the role that the random-link model plays for matching.

The monopartite Euclidean matching problem is the subject of items 1 and 2. Item 3 is the source's explicitly proposed separate generalization — a hope for future work on other systems; a full solution of finite-dimensional spin glasses is in any case a distinct and larger open problem.

References

M. Mézard and G. Parisi, "Replicas and optimization", Journal de Physique Lettres 46, 771-778 (1985). DOI: 10.1051/jphyslet:019850046017077100, https://doi.org/10.1051/jphyslet:019850046017077100.
M. Mézard and G. Parisi, "A replica analysis of the travelling salesman problem", Journal de Physique 47, 1285-1296 (1986). DOI: 10.1051/jphys:019860047080128500, https://doi.org/10.1051/jphys:019860047080128500.
M. Mézard and G. Parisi, "On the solution of the random link matching problems", Journal de Physique 48, 1451-1459 (1987). DOI: 10.1051/jphys:019870048090145100, https://doi.org/10.1051/jphys:019870048090145100.
Marc Mézard and Giorgio Parisi, "The Euclidean matching problem", Journal de Physique 49, 2019-2025 (1988). DOI: 10.1051/jphys:0198800490120201900, https://doi.org/10.1051/jphys:0198800490120201900.
David Sherrington and Scott Kirkpatrick, "Solvable Model of a Spin-Glass", Physical Review Letters 35, 1792-1796 (1975). DOI: 10.1103/PhysRevLett.35.1792, https://doi.org/10.1103/PhysRevLett.35.1792.
R. Brunetti, G. Parisi and F. Ritort, "On the replica symmetry for random weighted matchings", Journal of Physics A: Mathematical and General 24, 5077-5083 (1991). DOI: 10.1088/0305-4470/24/21/019, https://doi.org/10.1088/0305-4470/24/21/019.
J. H. Boutet de Monvel and O. C. Martin, "Mean field and corrections for the Euclidean minimum matching problem", Physical Review Letters 79, 167-170 (1997). DOI: 10.1103/PhysRevLett.79.167, https://doi.org/10.1103/PhysRevLett.79.167.
J. Houdayer, J. H. Boutet de Monvel and O. C. Martin, "Comparing mean field and Euclidean matching problems", The European Physical Journal B 6, 383-393 (1998). DOI: 10.1007/s100510050565, https://doi.org/10.1007/s100510050565.
Sergio Caracciolo, Carlo Lucibello, Giorgio Parisi and Gabriele Sicuro, "Scaling hypothesis for the Euclidean bipartite matching problem", Physical Review E 90, 012118 (2014). DOI: 10.1103/PhysRevE.90.012118, https://doi.org/10.1103/PhysRevE.90.012118.
Carlo Lucibello, Giorgio Parisi and 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.
Sergio Caracciolo, Matteo D'Achille and Gabriele Sicuro, "Random Euclidean matching problems in one dimension", Physical Review E 96, 042102 (2017). DOI: 10.1103/PhysRevE.96.042102, https://doi.org/10.1103/PhysRevE.96.042102.
Gabriele Sicuro, "The Euclidean Matching Problem", Springer Theses (Springer, 2017). DOI: 10.1007/978-3-319-46577-7, https://doi.org/10.1007/978-3-319-46577-7.
Sergio Caracciolo, Andrea Di Gioacchino, Marco Gherardi and Enrico M. Malatesta, "Solution for a bipartite Euclidean traveling-salesman problem in one dimension", Physical Review E 97, 052109 (2018). DOI: 10.1103/PhysRevE.97.052109, https://doi.org/10.1103/PhysRevE.97.052109.
Luigi Ambrosio, Federico Glaudo and Dario Trevisan, "On the optimal map in the 2-dimensional random matching problem", Discrete and Continuous Dynamical Systems - A 39, 7291-7308 (2019). DOI: 10.3934/dcds.2019304, https://doi.org/10.3934/dcds.2019304.
Michael Goldman and Dario Trevisan, "Optimal transport methods for combinatorial optimization over two random point sets", Probability Theory and Related Fields 188, 1315-1384 (2023). DOI: 10.1007/s00440-023-01245-1, https://doi.org/10.1007/s00440-023-01245-1.
Emanuele Caglioti and Francesca Pieroni, "Random matching in 2D with exponent 2 for Gaussian densities", Journal of Statistical Physics 191, 62 (2024). DOI: 10.1007/s10955-024-03275-y, https://doi.org/10.1007/s10955-024-03275-y.
Riccardo Piombo, Lorenzo Buffa, Dario Mazzilli and Aurelio Patelli, "Statistical mechanics of the Sub-Optimal Transport", Physica A: Statistical Mechanics and its Applications 131998 (2026). DOI: 10.1016/j.physa.2026.131998, https://doi.org/10.1016/j.physa.2026.131998.