Matching works

4 works

math.PR — Probability

Lower bounds for the Beardwood–Halton–Hammersley constant

Contributed by Tejasvi Singh Tomar

Let β\beta be the Beardwood–Halton–Hammersley constant: the shortest tour through nn independent uniform random points in the unit square has length asymptotic to βn\beta\sqrt n almost surely. Dong and Cao proved β≥0.6421\beta\ge0.6421 from an inequality β≥5/8+∑k=3KCk\beta\ge5/8+\sum_{k=3}^{K}C_k, where CkC_k is an integral over configurations of kk points in the plane that form a connected graph when points at distance at most 11 are joined. For C3C_3, C4C_4 and C5C_5, sharper bounds come from a first-order expansion of the area of the union of the unit disks on boxes of configurations. For C6+⋯+C22C_6+\dots+C_{22}, which Dong and Cao did not use, a lower bound comes from comparing each point only with the three points before it in the order of their first coordinates. We obtain β≥0.6496\beta\ge0.6496, and β≥0.6508\beta\ge0.6508 if the exponential function of the C library used to evaluate the bound for C6+⋯+C22C_6+\dots+C_{22} has a relative error below 10−910^{-9}. The proofs are computer-assisted; the bound 0.64960.6496 is proved in Lean 4, with finite checks evaluated by compiled code, from the inequality of Dong and Cao and two statements about unions of disks that we prove but do not formalize.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716094

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202621 pages
PDFView work

math.PR — Probability

The Ultimate Matching Theorem

Contributed by Michael Goldman, Francesco Grotto, Dario Trevisan

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.

Primarily AI-generated textHuman understanding: some parts
Nov 11, 202670 pages
PDFView work

math.PR — Probability

Quartic exponential matching in the unit square

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer

Take two independent samples of nn uniform points in the unit square. We prove that, with probability at least one half, the points can be paired so that the average of the exponential of the fourth power of the normalized pair distance is at most two. The distance normalization is Llog⁡n/nL\sqrt{\log n/n}, with LL an absolute constant. One pairing therefore satisfies both coordinate inequalities in the symmetric (4,4)(4,4) case of Talagrand's matching problem. The argument first controls a vector field transporting smoothed point densities, and then converts that control to a pairing. The main estimate comes from a Gaussian construction whose successive partitions depend only on noise already revealed; a correction using the classical bottleneck matching preserves the required density balance.

Primarily AI-generated textHuman understanding: all partsTalagrand matching problemgeometric probabilityrandom matching
Nov 11, 202613 pages
PDFView work

math.PR — Probability

On the Asymptotic W1W_1 Cost of Two-Dimensional Semi-Discrete Matching

Contributed by Heng Ma

Let X1,X2,…X_1,X_2,\ldots be independent uniform points in the unit square and let λ\lambda denote Lebesgue probability measure. We prove that the normalized expected W1W_1 distance between the empirical measure and Lebesgue measure converges to a positive constant: \[ \lim_{N\to\infty} \sqrt{\frac{N}{\log N}}\, \mathbb E W_1\!\left(\frac1N\sum_{i=1}^N\delta_{X_i},\lambda\right) =c_\star. \] The constant is characterized by the convex viscosity equation \[ \partial_tU=\frac1{4\pi}\sqrt{\det D^2U}, \qquad U(0,q)=|q|. \] Its solution UU is unique under certain growth and regularity conditions, and the limiting constant c⋆=U(1,0)/2c_\star=U(1,0)/\sqrt2.

Primarily AI-generated textHuman understanding: no parts
Sep 30, 202646 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations