The number of 4colorings of the Hamming cube
The number of 4colorings of the Hamming cube

Jinyoung Park, Rutgers University
Fine Hall 224
Let Q_d be the ddimensional 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 2colorings, but for q >2, the number of qcolorings of Q_d is highly nontrivial. Since Galvin (2002) proved that the number of 3colorings is asymptotically 6e2^{N/2}, the other cases remained open so far. In this talk, we prove that the number of 4colorings 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.