Bollobás–Meir conjecture for the power-weighted Euclidean traveling-salesman problem

From papers

For a finite set of points X[0,1]kX \subseteq [0,1]^k, let Sk(H)=eHekS_k(H)=\sum_{e\in H}|e|^k for a Hamiltonian cycle HH on XX, and let

SkHC(X):=minHSk(H),SkHC:=sup{SkHC(X):X[0,1]k, X finite}.S_k^{\mathrm{HC}}(X):=\min_H S_k(H),\qquad S_k^{\mathrm{HC}}:=\sup\{S_k^{\mathrm{HC}}(X):X\subseteq[0,1]^k,\ X\text{ finite}\}.

Bollobás–Meir conjecture. For any finite set of points X[0,1]kX\subseteq[0,1]^k, there exists a Hamiltonian cycle HH on XX with Sk(H)2kk/2S_k(H)\leq 2\cdot k^{k/2} if k3k\neq3, and S3(H)27/2S_3(H)\leq2^{7/2} if k=3k=3. Equivalently,

SkHC={2kk/2for k3,27/2for k=3.S_k^{\mathrm{HC}}=\begin{cases}2\cdot k^{k/2}&\text{for }k\neq3,\\2^{7/2}&\text{for }k=3. \end{cases}

The original Bollobás–Meir conjecture asserted the first value for every kk, but it was disproved in dimension 33 by Balogh, Clemen and Dumitrescu. The displayed statement is their adjusted conjecture, which remains open for all k>2k>2; the cases k=1,2k=1,2 are known.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Alexey Gordeev, “Bollobás-Meir TSP Conjecture Holds Asymptotically”, arXiv:2603.22010 (2026).

Solutions 0

No solutions have been posted yet.