Bollobás-Meir TSP Conjecture Holds Asymptotically

In 1992, Bollobás and Meir showed that for every $k\ge 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\mathrm{\mid }{x}_i-x_{i+1}{\mathrm{\mid }}^k\le c_k$, where $x_{n+1}=x_1$ and $\mathrm{\mid }x-y\mathrm{\mid }$ 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\mathrm{/}2}$ and showed that it cannot be taken lower than that. This conjecture was recently revised for $k=3$ by Balogh, Clemen and Dumitrescu, who showed that $c_3\ge 2^{7\mathrm{/}2}>2\cdot 3^{3\mathrm{/}2}$. It remains open for all $k>2$, with the best known upper bound $c_k\le {2.65}^k\cdot k^{k\mathrm{/}2}\cdot (1+o_k(1))$. We significantly narrow the gap between lower and upper bounds on $c_k$, reducing it from exponential to linear. Specifically, we prove that $c_k\le 2\mathrm{e}(k+1)\cdot k^{k\mathrm{/}2}$ and $c_k=k^{k\mathrm{/}2}\cdot (2+o_k(1))$, the latter establishing the conjecture asymptotically. We also obtain analogous results for related problems on Hamiltonian paths, spanning trees and perfect matchings in the unit cube. Our main tool is a new generalization of the ball packing argument used in earlier works.