12
$\begingroup$

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:


          LongestCubePath
          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.

$\endgroup$
  • $\begingroup$ (you mean "all the long diagonals and 3 of the others" I suppose) $\endgroup$ – Pietro Majer Apr 14 '18 at 18:25
  • 3
    $\begingroup$ Just to clarify: You are looking for the longest Hamiltonian path in a complete graph $G$ on $2^d$ vertices that has a length function on the edges of $G$ specified as follows: Each vertex in $G$ identified by a $d$-bit string, and the length of the edge, and the length of edge $\{u,v\}$ is the square root of the number of bits that $u$ and $v$ disagree in. (I mention this not to be pedantic, but because when I first read the problem my thought was that the underlying graph was the hypercube and you were allowed to shift only 1 bit at a time) $\endgroup$ – Mike Apr 14 '18 at 18:58
  • $\begingroup$ @Mike: Yes, your interpretation is correct: An edge of the path is just a segment in $\mathbb{R}^d$ connecting two vertices. Edges of the hypercube graph are just a subset of the possible segments in a longest path. $\endgroup$ – Joseph O'Rourke Apr 14 '18 at 19:28
  • $\begingroup$ See also the followup question, Longest simple path through hypercube corners. $\endgroup$ – Joseph O'Rourke Apr 15 '18 at 15:58
14
$\begingroup$

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}$.

$\endgroup$
  • 6
    $\begingroup$ It should probably be mentioned that if $P$ is a cycle (such as the Gray code), then the construction yields a Hamiltonian cycle of maximum length $2^{n-1}(\sqrt{n} + \sqrt{n-1})$. $\endgroup$ – Adam P. Goucher Apr 14 '18 at 23:54
3
$\begingroup$

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)$:


          Cuben2
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)$.
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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'$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.