# Are Gray codes in $\{0,1\}^n$ isomorphic?

Let $$n\in\mathbb{N}$$ be a positive integer. Two elements of $$\{0,1\}^n$$ form an edge if and only if their Hamming distance equals $$1$$. It is known that $$\{0,1\}^n$$ endowed with this graph structure possesses Hamiltonian cycles, also known as Gray codes.

If $$c_1, c_2$$ are Hamiltonian cycles in $$\{0,1\}^n$$, is there a graph isomorphism $$\varphi:\{0,1\}^n\to \{0,1\}^n$$ such that $$c_1$$ gets mapped onto $$c_2$$?

If you consider the Boolean addresses of points on the hypercube as base $$2$$ expansions of integers, then the vertices of the $$4$$-dimensional cube may be labeled $$0, 1, \ldots, 15$$. With this labeling, no two of the following Hamiltonian paths differ by a cube automorphism:

$$(0,2,6,7,15,14,10,8,12,13,9,11,3,1,5,4)$$,
$$(0,2,6,14,10,8,12,13,9,11,15,7,3,1,5,4)$$, and
$$(0,1,3,2,6,4,5,7,15,13,12,14,10,11,9,8)$$.

This is how I reasoned:

(1) The vertices of the $$n$$-cube may be identified with the points in $$\mathbb R^n$$ whose coordinates are in $$\{0,1\}^n$$. (Call this a geometric realization of the $$n$$-cube.) It is from this representation that points obtain Boolean addresses. For example, the vertex $$(0,1,0,1)\in\mathbb R^4$$ of the geometric realization of the $$4$$-cube has address 0101, hence will be labeled $$5$$.

(2) Any automorphism of the $$n$$-cube is determined by what it does on a single point and its immediate neighbors.

(3) It follows from (2) that each automorphism of the geometric realization from (1) is induced by a rigid motion of $$\mathbb R^n$$, since there are enough rigid motions to permute vertices transitively and then to permute the neighbors arbitrarily. The main point derived from this is that the automorphisms of the cube preserve its hyperfaces.

(4) From (3) we derive an invariant of Hamiltonian cycles in the $$n$$-cube: the $$n$$-term sequence of integers counting how many times the cycle is cut by hyperplanes which divide the cube into two parallel hyperfaces.

(5) The cut sequence for my first Hamiltonian cycle is $$(2,4,4,6)$$. The cut sequence for the second cycle is $$(2,2,4,8)$$. The cut sequence for the third cycle is $$(2,2,6,6)$$.

Here is an alternative way to view what is written above. My first Hamiltonian path, written in terms of Boolean addresses, is:

$${\small (0000,0010,0110,0111,1111,1110,1010,1000,1100,1101,1001,1011,0011,0001,0101,0100)}$$.

You can check that it is a Hamiltonian cycle by observing that exactly one bit changes each step of the cycle. The invariant of this cycle, which I called the cut sequence, is just the unordered sequence of the number of bit-changes per digit through the cycle. For example, the sequence of least significant digits of addresses in this Hamiltonian cycle is
$$(0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0)$$,
and there are four places in the cycle where the least significant bit changes. One can show that there are four places where the $$2$$nd-least significant bit changes, six places where the next least significant bit changes, and two places where the most significant bit changes. Thus, the (unordered) cut sequence is $$(4, 4, 2, 6)$$.

The second Hamiltonian cycle, written in terms of Boolean addresses is:

$${\small (0000,0010,0110,1110,1010,1000,1100,1101,1001,1011,1111,0111,0011,0001,0101,0100)}$$.

It is easy to read off that the $$3$$rd least significant digit goes through $$8$$ bit changes, which is the important distinction between the two Hamiltonian cycles.

The third Hamiltonian cycle is:

$${\small (0000,0001,0011,0010,0110,0100,0101,0111,1111,1101,1100,1110,1010,1011,1001,1000)}$$.

I did not locate any Hamiltonian cycle in $$\{0,1\}^4$$ with cut sequence $$(4,4,4,4)$$, but also I do not see a reason why such a Hamiltonian cycle cannot exist.

Edit.

To follow up on comments of Gerry Myerson and verret, it is shown in

Gilbert, E. N.
Gray codes and paths on the n-cube.
Bell System Tech. J 37 1958 815-826.

That there are 9 equivalence classes of Hamiltonian cycles in the 4-cube modulo the symmetry group of the cube. Also, it is shown in

Abbott, H. L.
Hamiltonian circuits and paths on the n-cube.
Canad. Math. Bull. 9 1966 557-562.

that the total number of Hamiltonian cycles in the $$n$$-cube is at least $$\left(7\sqrt{6}\right)^{2^n-4},$$ which grows doubly exponentially, while the size of the automorphism group of the $$n$$-cube is $$2^n\cdot n!$$, which grows singly exponentially $$\left(2^{O(n\log(n)}\right)$$.

These results provide a quick solution to this problem.

• It's interesting that you say the cut sequence (4,4,2,6) is unordered. I would say it is ordered by key, and not by value. Gerhard "Has Been Reviewing Python Dictionaries" Paseman, 2018.10.18. Oct 18, 2018 at 20:33
• I wonder whether an existence proof can be created by showing that there are fewer automorphisms than there are cyclic Gray codes. Oct 18, 2018 at 22:36
• @GerryMyerson Based on the (limited) data here ftp.inf.ethz.ch/doc/tech-reports/6xx/601.pdf, it does seem like the number of Hamiltonian cycles grows (much) more quickly than the size of the automorphism group (which is n!*2^n). Oct 18, 2018 at 22:50