The number of 4-colorings of the Hamming cube

2018/08/03 by Kahn, Jeff, Park, Jinyoung · 2 citations
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1808.01152

Abstract

Let Q_d be the d-dimensional hypercube and N=2^d. We prove that the number of (proper) 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.

Cited by

• Entropy methods in combinatorics
• Asymptotic enumeration via graph containers and entropy

Related

• The number of colorings of the middle layers of the Hamming cube
• New Results on Two Hypercube Coloring Problems
• The number of maximal independent sets in the Hamming cube
• The chromatic number of the square of the 8-cube
• Coloring the cube with rainbow cycles