Metraipolis › archive › dc_c2963d635e2c
A central limit theorem for the random assignment problem — arXiv:2608.05123
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.05123
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T11:38:53.472Z
- SHA-256 of the archived text
aeafb0cc578bb3e708b644e026a951b07168e341469e3c8b510880ce107269e9- Stable URL of this page
https://metraipolis.com/documento/dc_c2963d635e2c
How to cite
A central limit theorem for the random assignment problem — arXiv:2608.05123 — arXiv (en), https://arxiv.org/abs/2608.05123 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c2963d635e2c (Metraipolis archive dc_c2963d635e2c, sha256 aeafb0cc578bb3e708b644e026a951b07168e341469e3c8b510880ce107269e9)
BibTeX
@misc{dcc2963d635e2c,
title = {A central limit theorem for the random assignment problem — arXiv:2608.05123},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.05123},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c2963d635e2c; sha256 aeafb0cc578bb3e708b644e026a951b07168e341469e3c8b510880ce107269e9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.05123. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Let \(C_n\) be the minimum cost of a perfect matching in an \(n\times n\) matrix of independent uniform random variables. We prove that \[ \sqrt n\{C_n-\zeta(2)\} \ \Longrightarrow\ \mathcal N\bigl(0,4\zeta(2)-4\zeta(3)\bigr). \] The proof begins with an exact change of variables based on a uniformly rooted shortest-path selection of an optimal dual potential. After the unused reduced costs are integrated out, a reference law separates the rows conditionally on the potential field, while the ordered potential gaps become independent exponentials. The only residual dependence is a directed-tree factor. Ordering the potentials turns its zero--one support into a Ferrers matrix, whose matrix-tree determinant is triangular. A singular inverse-degree estimate and exact normalization then yield total-variation convergence to the reference law. Finally, a conditional triangular-array central limit theorem accounts for row noise, and a second triangular array accounts for the linear response of the potential field. The strategy used here is likely to be applicable to other problems.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in math.PR).
Categorie arXiv: Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2608.05123 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T11:29:05.125Z dalla pagina https://arxiv.org/catchup/math.PR/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).