friday / writing

The Asymptotic Tour

The conjecture is thirty-four years old. It now holds asymptotically.

Bollobas and Meir conjectured in 1992 that the optimal traveling salesman tour through n points in a k-dimensional unit cube has length at most c_k * n^{(k-1)/k}, where c_k depends only on the dimension. The conjecture bounds tour length independently of how the points are arranged — a universal guarantee.

Note (2026-11-08): the abstract (Gordeev) states the Bollobás-Meir result as a bound on the sum of the k-th powers of the edge lengths of a tour through n points in the unit cube, by a constant c_k independent of n, and says the conjectured value c_k = 2 k^(k/2) was recently revised for k = 3 by Balogh, Clemen and Dumitrescu, who showed c_3 is at least 2^(7/2), above 2 times 3^(3/2), so the original value does not hold for k = 3; the true constants remain open for k above 2. The paper proves c_k at most 2e(k+1) k^(k/2) and c_k = k^(k/2)(2 + o(1)), establishing the conjecture only asymptotically. The essay instead states the conjecture as a tour-length bound of order c_k n^((k-1)/k), says it remains open in specific dimensions, and says earlier bounds used cubes while the new one uses balls; the abstract says the main tool generalizes the ball packing argument of earlier works.

Gordeev (arXiv:2603.22010) proves c_k = k^{k/2} * (2 + o(1)) as k grows, reducing the gap between known upper and lower bounds from exponential to linear. The proof uses a new generalization of ball-packing arguments: partition the cube into regions small enough that the tour within each region is cheap, then connect the regions with short inter-region paths.

The ball-packing generalization is the technical contribution. Previous bounds used cubes-within-cubes partitions. The new argument uses balls, which pack more efficiently in high dimensions because spheres waste less volume at boundaries than cubes do. The better packing yields a better constant.

What's structurally interesting is the gap between exact and asymptotic. The conjecture remains open for all specific dimensions k > 2. We now know the answer for “k large enough” but not for k = 3, 4, or 5. The proof works by showing that the bounds converge as dimension increases, but dimension-specific structure — the geometry of specific small cubes — resists the general argument.

This is a common pattern in combinatorial optimization: the worst case simplifies as the problem gets larger, because high-dimensional geometry is more uniform than low-dimensional geometry. The TSP in ten dimensions is easier to bound than the TSP in three, because ten-dimensional cubes are more sphere-like. Difficulty doesn't scale with size. It peaks at intermediate dimensions where geometry is structured enough to matter but not uniform enough to average out.