{"id":"arxiv/2611.04699","url":"https://arxiv.org/abs/2611.04699","tags":["cs.DS","cs.DM","math.CO","math.PR"],"score":0,"title":"Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\\mathrm{e})Δ$ via Hidden Hard-Core Models","domain":"cs.DS","source":"arxiv","authors":["Xiongxin Yang"],"reviews":0,"subject":"cs.DS","summary":"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^2\\log q)$, whenever $q\\ge(1+1/\\mathrm{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/\\mathrm{e}\\approx1.368$ comes from the uniqueness threshold $\\approx\\mathrm{e}/Δ$ of the hard-core model on the infinite $Δ$-regular tree.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}