The Devil's Chessboard trick and coloring of the Hamming cube

Question

For $d \geq 2$, consider the $d$-dimensional Hamming cube $H_d$, i.e. the set of binary sequences $(b_0, b_1, \ldots, b_{d-1})$ with $b_k \in \{0,1\}$ of length $d$. Two such sequences are neighbors if they differ at exactly one position. The Hamming cube can be thought of as a $d$-regular graph with $2^d$ vertices. For what values of $d$ is it possible to color $H_d$ with $d$ colors such that, for any vertex $v \in H_d$, its $d$ neighbors have $d$ different colors. Note that, indeed, such a coloring does not prevent neighbors to share the same color.

It seems possible for $d=2^n$. For example, for $d=2$, one can color:

• $(0,0)$ and $(1,0)$ in red.
• $(0,1)$ and $(1,1)$ in blue.

Remark: such a coloring seems to give a solution toe the The Devil's Chessboard problem.

Answer 1

It is only possible for powers of $2$.

Suppose that one of the $d$ colors is red. We know that every vertex has exactly one red neighbor. So if you go through all $2^d$ vertices and, for each vertex $v$, draw an arrow from $v$ to its red neighbor, you will draw $2^d$ arrows. (Edges between two red vertices will have two arrows, one pointing each way.)

However, each red vertex has exactly $d$ arrows pointing to it: one from each of its neighbors! Since there are $2^d$ arrows, there are exactly $\frac{2^d}{d}$ red vertices. So $2^d$ must be divisible by $d$, which means $d$ must be a power of $2$.

The solution to the "Devil's Chessboard puzzle" also gives us a way to color the graph, when $d$ is a power of $2$.

Number the colors $0, 1, 2, \dots, d-1$. For each vertex $\mathbf b = (b_0, b_1, \dots, b_{d-1})$, let $I_{\mathbf b} = \{i : b_i = 1\}$: the set of positions that are $1$ in the vertex. Compute the number $n_{\mathbf b}$ obtained by a bitwise XOR of every element of $I_{\mathbf b}$, and color $\mathbf b$ with the color corresponding to that number.

For every $\mathbf b$, to the neighbor that differs from $b$ in the $i^{\text{th}}$ coordinate has the color corresponding to $n_{\mathbf b} \oplus i$ (where $i$ is bitwise XOR). As $i$ ranges over $0$ to $d-1$, so does $n_{\mathbf b} \oplus i$, so we see all the colors on the neighbors of $\mathbf b$.

(This only works for powers of $2$, because only in that case is $n_{\mathbf b}$ limited to the range $0, 1, \dots, d-1$.)

Answer 2

Although your precise question has already been answered, the solution motivates a natural minor variant of the question:

If $H_d$ can be coloured with $r$ colours, so that every vertex is adjacent to a vertex of each colour, must there exist a natural number $k$ with $r\leq2^k\leq d$?

The solution to the Devil's Chessboard problem implies that if such a $k$ exists for a given $d,r$, then so does a valid $r$-colouring of $H_d$ - just ignore the extra squares and extra possible values that can be communicated.

But are these the only values of $d,r$ for which a valid colouring exists? The accepted answer shows there are no other solutions where $d=r$ and it is not easy to find other solutions at all (even when $d$ is almost double $r$), which causes people to speculate that there are no other solutions. However researchers in the field have long known that there are other solutions. The example below was extracted from $[1]$.

Starting with a chessboard with a coin on each square, by flipping precisely one coin, we will show that it is possible to communicate any desired element of $\mathbb{F}_7^2$. This just shows that $d=64, r=49$ is possible, which is unremarkable. However in our example, turning any coin on the top row will have the same effect, allowing us to ditch $7$ squares, showing that $d=57, r=49$ is possible.

Consider each column of the chessboard separately. The solution to the Devil's Chessboard problem allows us to read off the position of a pawn somewhere on the column from the coins on that column, in such a way that by turning precisely one coin on the column, we can move the pawn to any desired square on the column. Further we can arrange the encoding so that flipping the coin on the top row does not move the pawn.

Now looking at the whole chessboard, we have encoded the position of a pawn on each column. By flipping one coin, we can move one pawn to any square on its column. There are also $8$ squares which do not move any of the pawns.

Label the columns of the chessboard with pairwise non-colinear elements of $\mathbb{F}_7^2$. For example: $$ \left(\begin{array}{c}0\\1\end{array}\right), \left(\begin{array}{c}1\\0\end{array}\right), \left(\begin{array}{c}1\\1\end{array}\right), \left(\begin{array}{c}1\\2\end{array}\right), \left(\begin{array}{c}1\\3\end{array}\right), \left(\begin{array}{c}1\\4\end{array}\right), \left(\begin{array}{c}1\\5\end{array}\right), \left(\begin{array}{c}1\\6\end{array}\right). $$

Label the rows of the chessboard with elements of $\mathbb{F}_7$, using all of them. For example: $0,1,2,3,4,5,6,6$.

The arrangement of pawns on the board gives us a linear combination of vectors: sum over pawns the coefficient of the row, multiplied by the vector of the column.

Now moving one of the $8$ pawns to one of the $6$ other coefficients results in changing the linear combination to one of $6\times 8=48$ vectors, different to the initial one. These are all distinct as the column vectors are pairwise non-colinear. Thus by flipping precisely one coin, we can communicate any element of $\mathbb{F}_7^2$. Further all the squares on the top row have the same effect, so we only need one of them.

$[1]$ Östergård, Patric R. J., A coloring problem in Hamming spaces, Eur. J. Comb. 18, No. 3, 303-309 (1997). ZBL0880.05033.The The accepted answer shows that