PreprintCC BY 4.0arXiv
Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ via Hidden Hard-Core Models
Abstract
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γ(n2log 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 ≈e/Δ of the hard-core model on the infinite Δ-regular tree.
Related
- Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
- Mixing profile for Glauber dynamics of the discrete Gaussian Free Field starting from super-harmonic functions
- Optimal Mixing of Glauber Dynamics for the Sherrington-Kirkpatrick Model at β< 1/2
- Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤ 1/2+ε
- Near linear mixing of random-cluster Glauber dynamics on random regular graphs
BibTeX
@misc{yang2026glauber,
title = {{Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrme)Δ$ via Hidden Hard-Core Models}},
author = {Xiongxin Yang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04699},
eprint = {2611.04699},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04699},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ via Hidden Hard-Core Models
AU - Xiongxin Yang
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04699
UR - https://arxiv.org/abs/2611.04699
AB - 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^2log 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 ≈e/Δ of the hard-core model on the infinite Δ-regular tree.
ER -