5
$\begingroup$

This is a variation on a previously answered question, Longest path through hypercube corners. Here I am seeking the longest simple (non-self-intersecting) path through the unit hypercube's vertices, composed of segments between vertices. (The segments need not follow the hypercube edges.) Without the simplicity requirement, MTyson showed that the longest path for the hypercube in $\mathbb{R}^d$ has length $$2^{d-1}\sqrt{d} + (2^{d-1}-1)\sqrt{d-1} \;.$$ For $d=3$, this length is $4\sqrt{3}+3\sqrt{2}$. In contrast, the longest simple path has length $\sqrt{3}+6\sqrt{2}$, as it can only use the $\sqrt{3}$ long diagonal once, and uses all six face $\sqrt{2}$-diagonals:

          CubeSimpPath
          Path: $(1,3,6,8,2,5,4,7)$. Length: $6\sqrt{2}+\sqrt{3} \approx 10.2$.
Motivation: This is in some (very loose) sense a Euclidean version of the Snake-in-a-box problem. (That problem asks for a path along hypercube edges that maintains at least a $1$-edge distance from itself.)

Added. For the tesseract, $d=4$, here is what I believe to be a simple path, which uses the long $2$-diagonal once (red below), eight $({=}2 d)$ $\sqrt{3}$-diagonals, and six $({=}\binom{d}{2})$ $\sqrt{2}$-diagonals (and no hypercube edges):

          TessSimp
          Path: $(1, 16, 5, 3, 15, 4, 2, 12, 6, 9, 11, 13, 10, 7, 14, 8)$. Length: $2 + 8 \sqrt{3} + 6 \sqrt{2} \approx 24.3$.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Note that two edges intersect if and only if their midpoints coincide, and a necessary condition is that the edges have equal length. $\endgroup$
    – Adam P. Goucher
    Commented Apr 15, 2018 at 13:33
  • 1
    $\begingroup$ An upper bound should arise from taking "the longest available diagonals". This involves 1 longest diagonal, 2*n second longest, 4*(n choose 2) third longest, up until you have chosen 2^n-1 diagonals. I suspect you can use symmetry to place the longest diagonal in the middle, and something like (inverted?) Gray codes for the lower levels. Gerhard "Call It Nested Gray Codes" Paseman, 2018.04.16. $\endgroup$
    – Gerhard Paseman
    Commented Apr 16, 2018 at 17:39
  • $\begingroup$ To focus your efforts, consider all midpoints of all faces. These will look like cube vertices, except you replace some of the coordinates which are 0 or 1 with 1/2. Choose 2^n - 1 of these midpoints with the goal of maximizing the total number of occurrences of 1/2. Now try to find a path through these mid points which is also Hamiltonian on the vertices, and such that the vertices which are path neighbors to a midpoint are face neighbors, meaning they agree on the coordinates that are not 1/2. Gerhard "This Is Multiply And Conquer" Paseman, 2018.04.16. $\endgroup$
    – Gerhard Paseman
    Commented Apr 16, 2018 at 17:53
  • $\begingroup$ @GerhardPaseman: Perhaps you meant $\binom{n}{2}$ 3rd longest, without the factor of $4$, in your upperbound? $\endgroup$
    – Joseph O'Rourke
    Commented Apr 18, 2018 at 14:29
  • $\begingroup$ I originally thought so, then I realized more was available. For a long diagonal that "misses" k dimensions, choose k binary coordinate positions (so n choose k), and then fix them to one of the 2^k coordinate values. So for k=2 I do want 4 as a multiplier. Gerhard "Otherwise I'm Using Every Size" Paseman, 2018.04.18. $\endgroup$
    – Gerhard Paseman
    Commented Apr 18, 2018 at 14:56

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .