HEXAGONbeta

The Ultimate Matching Theorem

Primarily AI-generated textHuman understanding: some partsmath.PR — Probability

Contributed by Michael Goldman ↗, Francesco Grotto ↗, Dario Trevisan ↗

Version 1 / Nov 11, 2026 / CC BY 4.0

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.

Provenance statement

This work was largely generated and proof-checked by LLMs through a series of interactions aimed at understanding the initial version of GPT-6's solution to Talagrand's Ultimate Matching problem. That solution was itself developed through extensive interactions with the LLM, drawing also on the authors' ideas and previous work. GPT-6 also provided a sharper argument for the endpoint cases of the conjecture, which is available together with the initial version of the solution in the GitHub repository referenced in the preprint. The authors have an overall understanding of the proofs and intend to provide a fully digested version in the near future.

Tools used

OpenAI
ChatGPT
Anthropic
Claude Fable

References

  1. M. Ajtai, J. Komlós and G. Tusnády, On optimal matchings , Combinatorica 4 (1984), 259--264.
  2. L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures , Birkhäuser, 2008.
  3. L. Ambrosio and F. Glaudo, Finer estimates on the 2-dimensional matching problem , J. Éc. polytech. Math. 6 (2019), 737--765.
  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.
  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.
  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.
  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.
  8. V. Armegioiu, M. Goldman, F. Grotto and D. Trevisan, Exact asymptotics for the 2D Euclidean random matching problem , arXiv:2609.08717 (2026).arXiv
  9. B. Bollobás and I. Leader, Edge-isoperimetric inequalities in the grid , Combinatorica 11 (1991), 299--314.
  10. J. Bretagnolle and P. Massart, Hungarian constructions from the nonasymptotic viewpoint , Ann. Probab. 17 (1989), 239--256.
Show all 28 referencesShow fewer references
  1. S. Caracciolo, C. Lucibello, G. Parisi and G. Sicuro, Scaling hypothesis for the Euclidean bipartite matching problem , Phys. Rev. E 90 (2014), 012118.
  2. X. Cheng, F. Otto, M. Palmieri and A. Wachtel, A geometrically linear approximation of min--max optimal matching , arXiv:2609.08680 (2026).arXiv
  3. R. M. Dudley, Uniform Central Limit Theorems , 2nd ed., Cambridge University Press, 2014.
  4. D. Gale, A theorem on flows in networks , Pacific J. Math. 7 (1957), 1073--1082.
  5. M. Goldman, M. Huesmann and F. Otto, Quantitative linearization results for the Monge--Ampère equation , Comm. Pure Appl. Math. 74 (2021), 2483--2560.
  6. 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.
  7. 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.
  8. M. Goldman and D. Trevisan, Optimal transport methods for combinatorial optimization over two random point sets , Probab. Theory Related Fields 188 (2024), 1315--1384.
  9. 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.
  10. 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.
  11. 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 (https://doi.org/10.13140/RG.2.2.26527.93606/2).DOI
  12. F. Santambrogio, Optimal Transport for Applied Mathematicians , Birkhäuser, 2015.
  13. M. Talagrand, Matching random samples in many dimensions , Ann. Appl. Probab. 2 (1992), 846--856.
  14. M. Talagrand, The Generic Chaining: Upper and Lower Bounds of Stochastic Processes , Springer, 2005.
  15. M. Talagrand, Upper and Lower Bounds for Stochastic Processes: Decomposition Theorems , 2nd ed., Springer, 2021.
  16. M. Talagrand, My favorite problems , manuscript, 2026.
  17. C. Villani, Optimal Transport: Old and New , Springer, 2009.
  18. https://github.com/grottofrancesco/UltimateMatchingTheorem.link

Version history

  1. v1 · 70 pagesSubmitted by Francesco GrottoInitial depositCurrentNov 10, 2026