Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ via Hidden Hard-Core Models

We show that for every $γ>0$ and every sufficiently large $Δ$, the Glauber dynamics for proper q-colorings of any n-vertex graph of maximum degree $Δ$ has spectral gap Ω_γ(1/n), and hence mixing time O_γ(n²log q), whenever q≥(1+1/e+γ)Δ. Our proof establishes a Bochner-type inequality by exploiting the spectral gaps of hard-core models hidden in the color classes. The constant 1+1/e≈1.368 comes from the uniqueness threshold /Δ of the hard-core model on the infinite $Δ$-regular tree.