3
$\begingroup$

I am trying to find a way to "travel" along each edge of a 6D hypercube once and only once. I know it is possible with a 2D square and a 4D tessarect. For the square, it is obvious how to accomplish this: Start at (0,0), move to (0,1), move to (1,1), move to (1,0), move to (0,0). Each edge has been traveled along only once. The tessarect is a bit more complicated, but it is possible (see the uploaded picture of the tessarect here). Start at 0000, and then move in the following order: 1000, 1100, 0100, 0000, 0001, 1001, 1101, 0101, 0001, 0011, 1011, 1111, 0111, 0011, 0010, 1010, 1000, 1001, 1011, 1010, 1110, 1100, 1101, 1111, 1110, 0110, 0100, 0101, 0111, 0110, 0010, 0000.

The 6-cube has stumped me. I am not sure how to move along every edge only once, but I assume that it is possible for all n-cubes where n is an even number. The following picture of a 6-cube may help. I have one colored so that each color represents the dimension that a certain edge is in. For example, an orange line represents an edge in the 1st dimension, between vertices 000000 and 000001. There is another picture of a 6-cube which in which all of the edges of a single 3D cube are colored similarly, and each cube is connected in higher dimensions through different colors.

Any help/insight is greatly appreciated, and please let me know if I need to elaborate. Thank you, Mitch

$\endgroup$
  • $\begingroup$ You might want to have a look at this. $\endgroup$ – amd May 5 '17 at 20:43
4
$\begingroup$

In general, finding an Eulerian tour of a connected graph where all degrees are even, such as any even-dimensional hypercube graph, is (1) always possible and (2) not hard to do algorithmically:

  1. Start by finding any cycle, just by taking arbitrary edges until you return to where you started.
  2. Pick a point on your cycle from which there are edges you haven't used yet. Start walking from that point until you get another cycle. Splice the second cycle into the first to create one bigger cycle.

This will let you solve the 6-dimensional case, but not produce a very nice description. Here's a recursive construction that takes a solution for the $n$-cube, and turns it into a solution for the $(n+2)$-cube. We write each coordinate as $(x,y_1,y_2)$, where $x$ is an $n$-dimensional coordinate (an element of $\{0,1\}^n$) and $y_1, y_2$ are each either $0$ or $1$.

  1. Take a tour of all the points of the form $(x,0,0)$ by using the $n$-dimensional solution.
  2. Modify it as follows: the first time a point $(x,0,0)$ is visited, splice in the cycle $$(x,0,0) \to (x,0,1) \to (x,1,1) \to (x,1,0) \to (x,0,0)$$ at that point in the tour.
  3. Modify that as follows: when you visit $(0^n,0,1)$ for the first time, splice in a tour of all points of the form $(x,0,1)$, using the $n$-dimensional solution again.
  4. Do step 3 for $(0^n,1,1)$ and $(0^n,1,0)$ as well.
$\endgroup$
  • $\begingroup$ Thank you very much! I have no experience with discrete mathematics, so this information might take a while to absorb, but I am certain is the solution that I am looking for. $\endgroup$ – Mitch D May 6 '17 at 19:05

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.