Jinyoung Park, Rutgers University

Abstract

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 of 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.