Let $Q_n$ denote the $n$-dimensional hypercube. It has a vertex for each binary string $x = x_n x_{n-1} \ldots x_1 \in \{0, 1\}^n$, and there is an edge between two vertices $v_x$ and $v_y$ if their corresponding binary strings $x$ and $y$ have Hamming distance one. For convenience, we will use $x$ to denote $v_x$ when the context is clear.
An $n$-bit gray code is a cyclic ordering of all $n$-bit binary strings such that consecutive strings in the code have Hamming distance one. Therefore, an $n$-bit gray code corresponds to a Hamiltonian cycle in $Q_n$. The Binary Reflected Gray Code (BRGC) is an example of such a code defined as follows, which we denote by $G_n$. For $n = 1$, $G_1$ is simply $[0; 1]$. For $n > 1$ is can be defined recursively by $G_n = 0 \cdot [G_{n - 1}]; 1 \cdot [G_{n-1}]^R$. In other words, $0 \cdot [G_{n - 1}]$ denotes the elements of $G_{n-1}$ prefixed by a $0$ and $1 \cdot [G_{n-1}]^R$ denotes the elements in $G_{n-1}$, in reversed order, prefixed by a $1$.
The BRGC has two useful properties. Let $G_n = [g_0; g_1; \ldots; g_{2^n - 1};]$ denote the elements of $G_n$.
- Bit $x_1$ is flipped every other time.
- For odd $i$, $0 \leq i \leq 2^n - 1$, define the pairs $P_{\lfloor \frac{i}{2} \rfloor} = (g_i, g_{i + 1 \mod 2^n})$. The elements of $Q_n$ can be partitioned into $2^{n-2}$ pairwise disjoint copies of $Q_2$ (isomorphic to $Q_2$), where each copy of $Q_2$ corresponds to two of the above pairs, which we denote by $S = (s_1, s_2)$ and $T = (t_1, t_2)$, such that $s_1 \oplus s_2 = t_1 \oplus t_2$ (the exclusive-or operator). Note that since $s_1$ occurs immediately before $s_2$ and $t_1$ occurs immediately before $t_2$ in $G_n$, then $s_1$ and $t_1$ have Hamming distance two. We can obtain such a partitioning as follows. The pairs $P_{2^{n-2} - 1}$ and $P_{2^{n-1} - 1}$ form one copy of $Q_2$, as well as the pairs $P_j$ and $P_{2^{n-1} - 2 - j}$, for $0 \leq j < 2^{n-2}-1$.
Is it possible to find a gray code (possibly by generalizing the BRGC), that admits a similar partitioning, except into $2^{n-3}$ disjoint copies of $Q_3$? I worry that the first property might prevent the generalization, but haven't been able to prove so.
If true, can something be said regarding a similar partitioning into $2^{n-d}$ disjoint copies of $Q_d$?
Example for $n=4$:
The vertices are labelled from $g_0$ to $g_{15}$, starting from the string of all zeros, denoting the order in the BRGC. The pairs $P_3$ and $P_7$ form one copy of $Q_2$, pairs $P_1$ and $P_5$ form another copy of $Q_2$, while the pairs $P_0$ and $P_6$, as well as $P_2$ and $P_4$, make the other two copies of $Q_2$.