The number of colorings of the middle layers of the Hamming cube

Abstract

For an odd integer $n=2d-1$, let ${\mathcal{B}}_d$ be the subgraph of the hypercube $Q_n$ induced by the two largest layers. In this paper, we describe the typical structure of proper $q$-colorings of $V({\mathcal{B}}_d)$ and give asymptotics on the number of them. The proofs use various tools including information theory (entropy), Sapozhenko's graph container method and a recently developed method of M. Jenssen and W. Perkins that combines Sapozhenko's graph container lemma with the cluster expansion for polymer models from statistical physics.

31 pages