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.

What was already known

Talagrand posed the simultaneous exponential-tail problem in Research Problem 17.1.2. The Ajtai–Komlós–Tusnády theorem gives the earlier worst-displacement scale for planar matching.

AI involvement AI-centered

The authors credit GPT-6 with the initial solution developed through extensive exchanges that used their ideas and earlier work. GPT-6 also found the endpoint asymptotic. Language models drafted and checked much of the manuscript during those exchanges.

Importance Notable

The result describes the critical tradeoff between the two coordinate bounds and separates the finite cases from the hard endpoints.

Technical verification Reported

The preprint gives the proof and describes model-assisted checking. It does not report a complete human proof check or a machine-checked proof.

Human understanding Few

The authors report an overall understanding and say they plan a fully worked-through account. The current manuscript was largely generated and checked by language models.

Other useful sources

Correction and publication history