Bollobás–Meir TSP Conjecture Holds Asymptotically
Alexey Gordeev · 2026
Read Bollobás–Meir TSP Conjecture Holds Asymptotically by Alexey Gordeev (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22010.txt.
Description
Gordeev studies a 1992 conjecture by Bollobás and Meir about short tours through points in a unit cube. The conjecture names the best constant in a tour-length bound that does not grow with the number of points. Gordeev proves the constant is at most a linear factor above the claimed value. In the limit, the value matches the conjecture, so it holds asymptotically. He also proves matching results for Hamiltonian paths, spanning trees, and perfect matchings. His main tool is a new form of the ball packing argument.
Catalog record
| CREATOR | Alexey Gordeev |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49707 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.22010