arXiv:2611.04699 · v1

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

首次提交 2026-11-03 19:22

版本更新 2026-11-03 19:22

雷达观测 2026-11-04 23:39

摘要

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.

作者备注：33 pages