Engbers–Galvin conjecture on colorings of the Hamming cube

Let QdQ_d be the dd-dimensional Hamming cube, let N=2dN=2^d be its number of vertices, and let Cq(Qd)C_q(Q_d) denote the number of proper qq-colorings of QdQ_d. For fixed qq, define

f(q)=q/22q/2(22q/2)d+q/22q/2(22q/2)d.f(q)=\frac{\lceil q/2\rceil}{2\lfloor q/2\rfloor}\left(2-\frac{2}{\lceil q/2\rceil}\right)^d+\frac{\lfloor q/2\rfloor}{2\lceil q/2\rceil}\left(2-\frac{2}{\lfloor q/2\rfloor}\right)^d.

Engbers–Galvin conjecture. For each fixed qq,

Cq(Qd)=(1+1{q odd})(qq/2)(q/2q/2)N/2exp[(1+o(1))f(q)]C_q(Q_d)=(1+\mathbf{1}_{\{q\text{ odd}\}})\binom{q}{\lfloor q/2\rfloor}(\lfloor q/2\rfloor\lceil q/2\rceil)^{N/2}\exp\bigl[(1+o(1))f(q)\bigr]

as dd\to\infty. The first factors count the choices of a main phase and the pure colorings with that phase, while the exponential accounts for isolated flaws. The conjecture is stated as the general fixed-qq prediction, although the paper notes that for q>4q>4 it can be weaker than the actual asymptotics.

Sources & referencesView supporting material

Primary source

Jeff Kahn and Jinyoung Park, “The number of 4-colorings of the Hamming cube”, arXiv:1808.01152 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.