Francesco Grotto

math.PR — Probability

The Ultimate Matching Theorem

Contributed by Michael Goldman, Francesco Grotto, Dario Trevisan

Let $X_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 $\alpha_1,\alpha_2>2$ with $1/\alpha_1+1/\alpha_2=1/2$, we prove that with probability tending to one a single permutation controls the $j$th coordinate displacements in the exponential Orlicz norm of exponent $\alpha_j$, at the scale $\sqrt{\log N/N}$, for both $j=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,\infty)$ and $(\infty,2)$ the conjecture fails: a Brownian local-time construction shows that the normalized optimal matching cost diverges in probability.