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

CREATORAlexey Gordeev
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49707
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.22010

Browse the full library · About the Tower of Babel