{"id":"arxiv/2603.22010","url":"https://arxiv.org/abs/2603.22010","tags":["math.CO","cs.CG","math.MG"],"score":0,"title":"Bollobás-Meir TSP Conjecture Holds Asymptotically","domain":"math.CO","source":"arxiv","authors":["Alexey Gordeev"],"reviews":0,"subject":"math.CO","summary":"In 1992, Bollobás and Meir showed that for every $k \\geq 1$ there exists a constant $c_k$ such that, for any $n$ points in the $k$-dimensional unit cube $[0, 1]^k$, one can find a tour $x_1, \\dots, x_n$ through these $n$ points with $\\sum_{i = 1}^n |x_i - x_{i + 1}|^k \\leq c_k$, where $x_{n + 1} = x_1$ and $|x - y|$ is the Euclidean distance between $x$ and $y$. Remarkably, this bound does not depend on $n$, the number of points. They conjectured that the optimal constant is $c_k = 2 \\cdot k^{k / 2}$ and showed that it cannot be taken lower than that. This conjecture was recently revised for…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-23","reactions":{}}