The number of 4-colorings of the Hamming cube

Let Q_d be the d-dimensional Hamming cube (hypercube) and N=2^d. We discuss the number of proper (vertex) colorings of Q_d given q colors. It is easy to see that there are exactly 2 proper 2-colorings, but for q>2, the number of q-colorings of Q_d is highly nontrivial. Since Galvin (2002) proved that the number of 3-colorings is asymptotically 6e2^{N/2}, the other cases remained open so far. In this talk, we prove that the number of 4-colorings of $Q_d$ is asymptotically 6e2^N, as was conjectured by Engbers and
Galvin in 2012. The proof uses a combination of information theory (entropy) and isoperimetric ideas originating in work of Sapozhenko in the 1980’s. This is joint work with Jeff Kahn.