betaFeedback

WorksMathematics

The Ultimate Matching Theorem

Abstract

Let X1,…,XNX_1,\dots,X_N be independent uniform points in the unit square, matched either to an evenly spread deterministic configuration or to a second independent sample. For exponents α1,α2>2\alpha_1,\alpha_2>2 with 1/α1+1/α2=1/21/\alpha_1+1/\alpha_2=1/2, we prove that with probability tending to one a single permutation controls the jjth coordinate displacements in the exponential Orlicz norm of exponent αj\alpha_j, at the scale log⁡N/N\sqrt{\log N/N}, for both j=1,2j=1,2. This settles Talagrand's Ultimate Matching Conjecture for all pairs of finite critical exponents. The proof constructs, on the flat torus, a current whose divergence is Gaussian white noise projected on a dyadic grid and whose coordinates have the critical anisotropic exponential Orlicz bounds, and transfers it to matching through a primal optimal-transport reduction. At the hard endpoints (2,∞)(2,\infty) and (∞,2)(\infty,2) the conjecture fails: a Brownian local-time construction shows that the normalized optimal matching cost diverges in probability.

Introduction

The matching problem

Let X1,…,XNX_1,\ldots,X_N be independent uniform points in the unit square D=[0,1]2D=[0,1]^2. Talagrand’s Ultimate Matching Conjecture, posed as Research Problem 17.1.2 (equation (17.3)) of [25], asks for a permutation matching this random sample to evenly spread deterministic points Y1,…,YNY_1,\ldots,Y_N with simultaneous exponential tail bounds in both coordinates. Here “evenly spread” has Talagrand’s meaning: DD admits a partition into NN rectangles of area 1/N1/N, with one point YiY_i in each rectangle RiR_i, such that Ri⊂B(Yi,10/N)R_i\subset B(Y_i,10/\sqrt{N}). We also consider the matching of two independent uniform samples, which satisfies the same conclusion. Our first result, which we call the Ultimate Matching Theorem, is the following.

Theorem 1.1. Let α1,α2\alpha_1,\alpha_2 be fixed finite exponents with

α1,α2>2,1α1+1α2=12.\alpha_1,\alpha_2 > 2,\qquad\frac{1}{\alpha_1}+\frac{1}{\alpha_2}=\frac{1}{2}.

There exists a constant L=L(α1,α2)>0L=L(\alpha_1,\alpha_2)>0, independent of NN and of the evenly spread configuration, such that the following holds with probability tending to one as N→∞N\to\infty: for every fixed evenly spread deterministic (Yi)i=1N(Y_i)_{i=1}^N, or when (Yi)i=1N(Y_i)_{i=1}^N is a second independent uniform sample, one and the same permutation π∈SN\pi\in S_N satisfies, for both coordinates j=1,2j=1,2,

∑i=1Nexp⁡[(N∣Xij−Yπ(i)j∣Llog⁡N)αj]≤2N,j=1,2.(1)\sum_{i=1}^{N}\exp\left[\left(\frac{\sqrt{N}\lvert X_i^j-Y_{\pi(i)}^j\rvert}{L\sqrt{\log N}}\right)^{\alpha_j}\right]\leq2N,\qquad j=1,2. \tag*{(1)}

The symmetric quartic case (4,4)(4,4) is included. The proof is completed in Corollaries 18.1 and 16.1, which combine the Gaussian flow estimate of Theorem 2.1 with the reduction of Part II.

Finite subcritical exponents. The theorem also gives (1.1) for every fixed pair 0<α1,α2<∞0<\alpha_1,\alpha_2<\infty with α1−1+α2−1>1/2\alpha_1^{-1}+\alpha_2^{-1}>1/2, after changing the constant LL. Indeed, set

c=2(α1−1+α2−1)>1,ri=cαi.c=2(\alpha_1^{-1}+\alpha_2^{-1})>1,\qquad r_i=c\alpha_i.

Then ri>αir_i>\alpha_i, ri>2r_i>2, and r1−1+r2−1=1/2r_1^{-1}+r_2^{-1}=1/2, so the critical theorem applies with exponents r1,r2r_1,r_2. For the resulting permutation, write ti,j=N∣Xij−Yπ(i)j∣/(Llog⁡N)t_{i,j}=\sqrt{N}\lvert X_i^j-Y_{\pi(i)}^j\rvert/(L\sqrt{\log N}). Since tαj≤1+trjt^{\alpha_j}\leq1+t^{r_j} for t≥0t\geq0, Jensen’s inequality with a fixed A≥1A\geq1 gives

1N∑i=1Ne(ti,j/A)αj≤(1N∑i=1Neti,jαj)A−αj≤(2e)A−αj≤2\frac{1}{N}\sum_{i=1}^{N}e^{(t_{i,j}/A)^{\alpha_j}}\leq\left(\frac{1}{N}\sum_{i=1}^{N}e^{t_{i,j}^{\alpha_j}}\right)^{A^{-\alpha_j}}\leq(2e)^{A^{-\alpha_j}}\leq2

when Aαj≥log⁡(2e)/log⁡2A^{\alpha_j}\geq\log(2e)/\log2 for both j=1,2j=1,2. Thus the same permutation works at the same scale, with LL replaced by ALAL; the probability of success is unchanged.

The hard endpoints. The coordinate endpoints (2,∞)(2,\infty) and (∞,2)(\infty,2) behave differently. Theorem 20.1 in Part III shows that there the optimal matching cost, divided by log⁡N/N\sqrt{\log N/N}, diverges in probability, uniformly over deterministic reference configurations. The Gaussian construction of Part I applies only to finite exponents, and the endpoint obstruction is of a different nature. These coordinatewise endpoints should not be confused with the usual scalar L∞L^\infty matching problem or with an endpoint of a power-cost problem. In the endpoint cases it is in fact possible to determine the exact first order asymptotic (in probability) behavior of the cost: for its (undigested, AI assisted) derivation we refer once again to the associated GitHub repository [28], since here we are mainly interested in the failure of Talagrand’s conjecture.

Previous work

The dual route. The foundations of planar random matching go back to Ajtai, Komlós and Tusnády [1]. Talagrand’s work [23, 24, 25] identified the multiscale nature of the problem and led to Research Problem 17.1.2 in the 2021 monograph. The guiding method is dual: one estimates transport or discrepancy functionals against classes of test functions, and controls the resulting random suprema through chaining, majorizing measures and geometric decompositions. This approach has produced sharp matching estimates in several regimes.

In dimension three, Chapter 18 of [25] proves a sharp matching theorem between an independent uniform sample and an evenly spread deterministic configuration, including coordinate-dependent exponential costs and hard coordinate constraints (Theorem 18.1.1 and Exercise 18.1.4); Talagrand observes that the extension to dimensions d>3d > 3 requires no new ideas. Above dimension two, irregularities at different scales cannot accumulate in the same way, whereas in the plane their cumulative effect produces the critical logarithmic factor. The remaining difficulty is therefore specifically two-dimensional.

The dual direction continues to develop: Cheng, Otto, Palmieri and Wachtel [12] study min–max matching through a geometrically linear approximation of a dual formulation, and Ouimet [21] proposes a solution to Problem 5.3 in Talagrand’s My favorite problems [26], controlling simultaneously total distance and maximal displacement through electrical flows and planar Lipschitz truncation of lattice circulations.

The primal route. Our proof follows a complementary tradition. Rather than estimating the dual supremum, we construct an actual primal transport current carrying the discrepancy of the random measures. This approach was brought into focus by the statistical-physics prediction of Caracciolo, Lucibello, Parisi and Sicuro [11]: at leading order in quadratic bipartite matching, the displacement should behave like the gradient of a Poisson potential driven by empirical-density fluctuations, which is the linearization of the Monge–Ampère equation. Ambrosio, Stra and Trevisan [6] established the leading two-dimensional quadratic asymptotics rigorously, and finer results on the cost and the optimal map followed [3, 4]. In parallel, the variational regularity theory of optimal transport, through the harmonic approximation of Goldman and Otto [17] and its quantitative versions by Goldman, Huesmann and Otto [15, 16], quantified the approximation of displacements by Poisson fluxes; related methods treat nonuniform planar domains [5]. These results make it natural to study random matching through the Eulerian continuity equation and a compatible vector current.

For nonquadratic costs the corresponding equation is nonlinear. Ambrosio, Vitillaro and Trevisan [7] obtained sharp estimates for power-law costs, and Armegioiu, Goldman, Grotto and Trevisan [8] related finite power-cost asymptotics on the torus to a Gaussian variational-martingale problem and a parabolic Monge–Ampère Bellman equation. In this viewpoint successive logarithmic scales are accumulated through stochastic control; it directly motivates the construction of Part I. The power-cost results do not, by themselves, give the coordinatewise exponential Orlicz bounds proved here.

Strategy of the proof

Critical Gaussian currents. The main analytic task is to solve a divergence equation for mean-zero Gaussian white noise projected onto dyadic squares of mesh h=2−mh = 2^{-m} on the flat two-dimensional torus. With ψr(t)=e∣t∣r−1\psi_r(t) = e^{|t|^r} - 1 and ∥⋅∥ψr\lVert\cdot\rVert_{\psi_r} the associated Luxemburg norm, Part I constructs, with probability bounded below uniformly in mm, a periodic current JJ with

div⁡J=Wh,max⁡i=1,2∥Ji∥ψri≤Cm,\operatorname{div} J = W_h,\qquad\max_{i=1,2} \lVert J_i\rVert_{\psi_{r_i}} \le C\sqrt{m},

for every finite critical pair (r1,r2)=(α1,α2)(r_1,r_2) = (\alpha_1,\alpha_2) (Theorem 2.1). The difficulty is not the existence of an inverse of the divergence, but the selection of one whose two coordinate tails are simultaneously of the critical size.

At a single point, a Bellman equation suggests an inverse-Hessian covariance for a Gaussian martingale, and a supersolution evaluated backward in Bellman time formally gives a supermartingale. The pointwise choice, however, need not be compatible across space. Part I therefore reveals the Gaussian increments through predictable local divergence corrections on anisotropic Whitney cells. An adaptive metric follows the locally preferred covariance, and a discounted memory records spatial oscillations of the accumulated current. A simultaneous induction on the metric and the memory yields a contracting Lyapunov quantity, whose negative drift pays for the variance of the critical exponential tilt. A terminal Gaussian correction then transfers the current from the adaptive partition to the fixed dyadic grid.

From currents to matching. Part II supplies the reductions, independently of the adaptive construction. The minimum-flow gauge is uniformly Lipschitz in the dyadic Gaussian coefficients, so a fixed positive success probability upgrades to high probability by Gaussian concentration. An exact four-sheet folding transfers the torus estimate to the square. Dyadic regularization, a comparison between transport and static currents, and an interval-encoded KMT coupling relate the Gaussian source to one empirical histogram against Lebesgue measure, and then to two independent histograms. Talagrand’s evenly spread points are a further O(N−1/2)O(N^{-1/2}) transport from Lebesgue measure, and a Birkhoff decomposition yields one permutation with both coordinate bounds. These steps give (1.1) in both formulations.

The endpoint obstruction. At the endpoint (2,∞)(2,\infty) the reduction of Part II still applies, so it suffices to show that the square Gaussian minimum-flow gauge is not of order m\sqrt{m}. Part III builds random dual test potentials of bounded cost whose expected pairing with the projected noise is too large. The input is a planar Brownian martingale with bounded terminal anisotropic Orlicz cost but arbitrarily large expected integrated square-root determinant, obtained from short Brownian local-time stages. An adaptive tree of piecewise affine Gaussian bubbles converts this determinant into a positive Gaussian pairing.

Organization

Part I (Sections 2–8) proves the Gaussian flow estimate on the torus; the geometric estimates for its adaptive construction are collected in Appendix A. Part II (Sections 9–19) reduces matching to the square Gaussian flow problem, upgrades fixed-probability bounds to high probability, transfers the torus estimate to the square, and completes the proof of Theorem 1.1. Part III (Sections 20–24) proves the failure at the hard endpoints.

I Critical Gaussian Orlicz flows on the torus

In this part, WhW_h is the projection of mean-zero Gaussian white noise on the flat torus T2\mathbb{T}^2 onto the dyadic square grid of mesh h=2−mh=2^{-m}. For fixed 2<r1,r2<∞2<r_1,r_2<\infty with 1/r1+1/r2=1/21/r_1+1/r_2=1/2, we bound the minimum coordinatewise Orlicz norm of a periodic current with divergence WhW_h by a multiple of m\sqrt{m}, with probability bounded below independently of mm (Theorem 2.1). The construction combines predictable Gaussian increments, local inverses of the divergence in anisotropic Whitney charts, and a contracting metric–memory functional. A terminal Gaussian correction transfers the adaptive current to the fixed dyadic source.

The Gaussian flow problem and the strategy

The Gaussian minimum-flow problem

Let WW be mean-zero real white noise on the flat torus T2\mathbb{T}^2:

EW(f)W(g)=∫T2fg−∫T2f∫T2g.(2)\mathbb{E}W(f)W(g)=\int_{\mathbb{T}^2}fg-\int_{\mathbb{T}^2}f\int_{\mathbb{T}^2}g. \tag*{(2)}

For h=2−mh=2^{-m}, let PhP_h denote averaging on the fixed periodic hh-square grid and write Wh=PhWW_h=P_hW; thus Wh∣Q=h−2W(Q)W_h|_Q=h^{-2}W(Q) and ∫T2Wh=0\int_{\mathbb{T}^2}W_h=0. We use the Luxemburg norm ∥⋅∥ψr\|\cdot\|_{\psi_{r}} associated with ψr(t)=e∣t∣r−1\psi_r(t)=e^{|t|^r}-1. Fix finite exponents ri>2r_i>2 on the critical line

ai=1ri,a1+a2=12.(3)a_i=\frac{1}{r_i},\qquad a_1+a_2=\frac{1}{2}. \tag*{(3)}

We also set a∗:=max⁡iai<1/2a_*:=\max_i a_i<1/2. For every mean-zero source ff, define the minimum-flow gauge

F~r(f)=inf⁡div⁡J=fmax⁡i=1,2∥Ji∥ψri.(4)\widetilde{\mathcal{F}}_r(f)=\inf_{\operatorname{div}J=f}\max_{i=1,2}\|J_i\|_{\psi_{r_i}}. \tag*{(4)}

References

  1. [1]M. Ajtai, J. Komlós and G. Tusnády, On optimal matchings, Combinatorica 4 (1984), 259–264.DOI
  2. [2]L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures, Birkhäuser, 2008.
  3. [3]L. Ambrosio and F. Glaudo, Finer estimates on the 2-dimensional matching problem, J. Éc. polytech. Math. 6 (2019), 737–765.arxiv.org/abs/1810.07002
  4. [4]L. Ambrosio, F. Glaudo and D. Trevisan, On the optimal map in the 2-dimensional random matching problem, Discrete Contin. Dyn. Syst. 39 (2019), 7291–7308.arxiv.org/abs/1903.12153
  5. [5]L. Ambrosio, M. Goldman and D. Trevisan, On the quadratic random matching problem in two-dimensional domains, Electron. J. Probab. 27 (2022), paper no. 54.arxiv.org/abs/2110.14372
  6. [6]L. Ambrosio, F. Stra and D. Trevisan, A PDE approach to a 2-dimensional matching problem, Probab. Theory Related Fields 173 (2019), 433–477.arxiv.org/abs/1611.04960
  7. [7]L. Ambrosio, F. Vitillaro and D. Trevisan, Sharp PDE estimates for random two-dimensional bipartite matching with power cost function, Rend. Lincei Mat. Appl. 35 (2024), 323–342.arxiv.org/abs/2405.09397
  8. [8]V. Armegioiu, M. Goldman, F. Grotto and D. Trevisan, Exact asymptotics for the 2D Euclidean random matching problem, arXiv:2609.08717 (2026).arxiv.org/abs/2609.08717
  9. [9]B. Bollobás and I. Leader, Edge-isoperimetric inequalities in the grid, Combinatorica 11 (1991), 299–314.
  10. [10]J. Bretagnolle and P. Massart, Hungarian constructions from the nonasymptotic viewpoint, Ann. Probab. 17 (1989), 239–256.DOI
  11. [11]S. Caracciolo, C. Lucibello, G. Parisi and G. Sicuro, Scaling hypothesis for the Euclidean bipartite matching problem, Phys. Rev. E 90 (2014), 012118.DOI
  12. [12]X. Cheng, F. Otto, M. Palmieri and A. Wachtel, A geometrically linear approximation of min–max optimal matching, arXiv:2609.08680 (2026).arxiv.org/abs/2609.08680
  13. [13]R. M. Dudley, Uniform Central Limit Theorems, 2nd ed., Cambridge University Press, 2014.
  14. [14]D. Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957), 1073–1082.
  15. [15]M. Goldman, M. Huesmann and F. Otto, Quantitative linearization results for the Monge–Ampère equation, Comm. Pure Appl. Math. 74 (2021), 2483–2560.
  16. [16]M. Goldman, M. Huesmann and F. Otto, Almost sharp rates of convergence for the average cost and displacement in the optimal matching problem, preprint, 2023; Abel Symposium proceedings.arxiv.org/abs/2312.07995
  17. [17]M. Goldman and F. Otto, A variational proof of partial regularity for optimal transportation maps, Ann. Sci. Éc. Norm. Supér. 53 (2020), 1209–1233.arxiv.org/abs/1704.05339
  18. [18]M. Goldman and D. Trevisan, Optimal transport methods for combinatorial optimization over two random point sets, Probab. Theory Related Fields 188 (2024), 1315–1384.arxiv.org/abs/2209.14615
  19. [19]A. J. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, in: Combinatorial Analysis, Proc. Sympos. Appl. Math. 10, Amer. Math. Soc., Providence, 1960, 113–127.
  20. [20]J. Komlós, P. Major and G. Tusnády, An approximation of partial sums of independent RV’s and the sample DF, I, Z. Wahrscheinlichkeitstheorie verw. Gebiete 32 (1975), 111–131.
  21. [21]F. Ouimet, A solution to Problem 5.3 in Talagrand’s My Favorite Problems: simultaneous sum and bottleneck bounds for random planar matchings, preprint (2026), doi:10.13140/RG.2.2.26527.93606/2.DOI
  22. [22]F. Santambrogio, Optimal Transport for Applied Mathematicians, Birkhäuser, 2015.DOI
  23. [23]M. Talagrand, Matching random samples in many dimensions, Ann. Appl. Probab. 2 (1992), 846–856.DOI
  24. [24]M. Talagrand, The Generic Chaining: Upper and Lower Bounds of Stochastic Processes, Springer, 2005.DOI
  25. [25]M. Talagrand, Upper and Lower Bounds for Stochastic Processes: Decomposition Theorems, 2nd ed., Springer, 2021.
  26. [26]M. Talagrand, My favorite problems, manuscript, 2026.
  27. [27]C. Villani, Optimal Transport: Old and New, Springer, 2009.
  28. [28]https://github.com/grottofrancesco/UltimateMatchingTheorem.

Paper details

vlnc:W_8ekwnwtm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI ChatGPT, Anthropic Claude Fable

View statement
Looking for related papers…
Contents