The number of 4-colorings of the Hamming cube

Jeff Kahn, Jinyoung Park

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Let Qd be the d-dimensional hypercube and N = 2d. We prove that the number of (proper) 4-colorings of Qd is asymptotically 6e2N, 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.

Original languageEnglish (US)
Pages (from-to)629-649
Number of pages21
JournalIsrael Journal of Mathematics
Volume236
Issue number2
DOIs
StatePublished - Mar 1 2020

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The number of 4-colorings of the Hamming cube'. Together they form a unique fingerprint.

Cite this