Talagrand’s ultimate matching problem in the plane

Match independent uniform points in a square to evenly spread reference points. Can one pairing control large displacements in both coordinates at the same time, with a different exponential tail bound in each coordinate?

Why it matters and what counts as progress

Why it matters: Random samples have local surpluses and shortages. The problem asks how tightly one pairing can control movement in two directions when it balances those fluctuations.

What counts as progress: Prove simultaneous bounds for one pairing with probability tending to one as the sample grows. Establish the scale at the critical exponent pairs and determine what happens when one coordinate is subject to a hard maximum.

How the problem developed

  1. 1984 · Planar matching bound [4]

    Miklós Ajtai, János Komlós and Gábor Tusnády Established the worst-displacement scale for planar random matching.

  2. 2021 · Problem statement [3]

    Michel Talagrand Asked for simultaneous coordinatewise exponential bounds for one pairing in the plane.

  3. 11 Nov 2026 · Critical exponent theorem [1][2]

    Michael Goldman, Francesco Grotto and Dario Trevisan with GPT-6 Posted a proof for the finite critical pairs and an obstruction at the hard endpoints.

AI contribution

The Ultimate Matching Theorem

Michael Goldman, Francesco Grotto, Dario Trevisan

Goldman, Grotto and Trevisan report that with probability tending to one, a single pairing controls both coordinate displacements at scale log⁡N/N\sqrt{\log N/N} for every fixed pair of finite exponents above two whose reciprocals add to one half. They prove that this scale fails when one exponent is two and the other is infinity.

AI involvementAI-centered
ImportanceNotable
Technical verificationReported
Human understandingFew
Paper date:

Sources

  1. The Ultimate Matching Theorem
  2. The authors’ account of GPT-6’s role
  3. Talagrand, Upper and Lower Bounds for Stochastic Processes
  4. Ajtai, Komlós and Tusnády, On optimal matchings
  5. Original proof drafts and supporting material
Publication history