Engbers–Galvin conjecture on colorings of the Hamming cube

About 8 years old · traced to

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/2⌉2⌊q/2⌋(2−2⌈q/2⌉)d+⌊q/2⌋2⌈q/2⌉(2−2⌊q/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})(q⌊q/2⌋)(⌊q/2⌋⌈q/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 d→∞d\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.

References

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.