Longest path through hypercube corners

Question

Is the longest Hamiltonian path through the $2^d$ unit hypercube vertices known, where path length is measured by Euclidean distance in $\mathbb{R}^d$? The unit hypercube spans from $(0,0,\ldots,0)$ to $(1,1,\ldots,1)$.

For example, for the cube in $\mathbb{R}^3$, I believe the longest path has length $3\sqrt{2}+4\sqrt{3} \approx 11.17$, avoiding all edges of length $1$, and using all $4$ of the long diagonals and $3$ short diagonals:

---

         
          ^{Path: $(1,7,2,8,3,5,4,6)$.}

---

This likely has been studied, in which case pointers would be appreciated. If exact values are not known, bounds would be useful.

Answer 1

Take a Hamiltonian path $P$ of minimal length on the $n-1$-cube, which has length $2^{n-1}-1$. Construct a path $Q$ in the $n$-cube as follows. For each edge $(e_1,\dots,e_i,\dots,e_{n-1})\to(e_1,\dots,1-e_i,\dots,e_{n-1})$ in P add edges $(e_1,\dots,e_i,\dots,e_{n-1},0)\to(1-e_1,\dots,1-e_i,\dots,1-e_{n-1},1)$ and $(1-e_1,\dots,1-e_i,\dots,1-e_{n-1},1)\to(e_1,\dots,1-e_i,\dots,e_{n-1},0)$ to $Q$. Add the final long diagonal to $Q$. In the end $Q$ is Hamiltonian and has the maximal length $2^{n-1}\sqrt{n}+(2^{n-1}-1)\sqrt{n-1}$.

Answer 2

Illustrating @MTyson's construction for $d=n=2$. We start with an edge $(0,1)$ for the $1$-cube, and replace $(0,1)$ with $(0,0),(1,1)$ and $(1,1),(1,0)$. This leaves one final long diagonal $(1,0),(0,1)$:

---

         

---

And the length of the path is $$ 2^1 \sqrt{2} + (2^1 -1 ) \sqrt{1} = 2 \sqrt{2} + 1 \;. $$

For $d=n=3$, MTyson's construction yields exactly the path I illustrated: $(1, 7, 2, 8, 3, 5, 4, 6)$. Here I will use the vertex indices illustrated in the main post, rather than the coordinates.

• One starts with the $2$-cube path $(1,2,3)$.
• The $(1,2)$ edge is replaced by $(1,7,2)$.
• The $(2,3)$ edge is replaced by $(2,8,3)$.
• The $(3,4)$ edge is replaced by $(3,5,4)$.
• Finally, the last diagonal is added: $(4,6)$.

Answer 3

We can in fact, a corrollary from MTyson's post is that we can construct a graph $G$ isomorphic to a hypercube $H$ (where the vertices are the $d$-bit strings and two vertices are adjacent in $H$ if they differ in precisely one bit) such that every edge in $G$ has length at least $\sqrt{d-1}$ in this metric, and $G$ admits a Hamiltonian circuit where half the edges have length $\sqrt{d}$.

Vertex $(u_1,u_2,\ldots, u_d)$ is adjacent in $G$ to $(1-u_1,1-u_2,\ldots, 1-u_{i-1}, u_i, 1-u_{i+1}, \ldots, 1-u_d)$ for all $i=1,2,\ldots, d-1$, and then vertex $(u_1,u_2, \ldots, u_d)$ is also adjacent in $G$ to its opposite $\bar{u}= (1-u_1,1-u_2, \ldots, 1-u_d)$.

Then $G$ is indeed isomorphic to a hypercube $H$ and has all edges of length at least $\sqrt{d-1}$. Furthermore, as $H$ admits a Hamiltonian circuit that has all edges of the form $\{(u_1, u_2, \ldots, u_{d-1}, u_d), (u_1, u_2, \ldots, u_{d-1}, 1-u_d)\}$ (i.e., the vertices differ in precisely their last bit), it follows that $G$ admits a Hamiltonian circuit that has all edges $\{u,\bar{u}\}$.

One can also check that no Hamiltonian cycle can have longer length than $2^{d-1}(\sqrt{d} + \sqrt{d-1})$. Indeed, for each vertex $u$, there is only one other vertex that is $\sqrt{d}$ distance from $u$. So this implies that the edges $\{e = \{u,v\}; ||u-v||_2 = \sqrt{d} \}$ form a matching. Thus only half of the edges $e$ in a Hamiltonian cycle can have length $\sqrt{d}$, the remaining must have length no more than $\sqrt{d-1}$, giving the upper bound.

Answer 4

The upper bound for the length of such a path is of course $2^d\sqrt{d}$.

1. A random ordering of the vertices has to give you an approximation to within $\frac{1}{\sqrt{2}}$; if $u$ and $v$ are randomly chosen, then they should differ in expected $\frac{d}{2}$ bits.

2. The following recursion has to come pretty close to $2^d\sqrt{d}$: Find a long Hamiltonian path $P_{d/2}$ on a hypercube $H_{d/2}$ w $2^{d/2}$ vertices, and order the vertices by where they are on $P_{d/2}$. Let $u$ and $v$ be adjacent vertices in $P_{d/2-1}$ such that $u$ comes before $v$. Then for each edge $\{u',v'\}$ in $P_{d/2-1}$, put the edge between $u1u'$ and $v0v'$.