Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
Abstract
We study the mixing time of the single-site Glauber dynamics for sampling proper q-colorings on sparse Erdős-Rényi random graphs 𝒢(n, d/n). We prove that, whenever q ≥ (1 + od(1))d, Glauber dynamics mixes in polynomial time with high probability over 𝒢(n, d/n) for all sufficiently large integer n. This improves the previous bound q = (α* + od(1))d where α* = 1.7632... is the unique solution of x = exp(1/x) on [1, ∞) by Efthymiou, Hayes, Štefankovič, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold on infinite regular trees. Our proof has three main ingredients. First we establish logarithmic bounds on the spectral and coupling independence constants of the Gibbs distribution by extending the tree analysis of Chen, Liu, Mani, and Moitra (J. ACM, 2026). Second, we extend the entropy-factorization framework for two-spin systems on random graphs, developed by Bezáková, Galanis, Goldberg, and Štefankovič (TALG, 2024), to proper colorings by introducing a buffer around high-degree vertices. Finally, we compare the resulting heat-bath block dynamics with the single-site Glauber dynamics.
Related
- Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ via Hidden Hard-Core Models
- Sampling Line-Graph Colorings with Constant Extra Colors
- Thresholds and Fluctuations for Colorful Arithmetic Progressions in Sparse Random Colorings
- Multiset Colorings of Random Graphs Across Density Regimes
- Uniqueness and nonuniqueness in the disjoint data inverse problem: a sharp spectral threshold
BibTeX
@misc{li2026rapid,
title = {{Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold}},
author = {Zhidan Li and Kuan Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25391},
eprint = {2610.25391},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25391},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
AU - Zhidan Li
AU - Kuan Yang
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2610.25391
UR - https://arxiv.org/abs/2610.25391
AB - We study the mixing time of the single-site Glauber dynamics for sampling proper q-colorings on sparse Erdős-Rényi random graphs 𝒢(n, d/n). We prove that, whenever q ≥ (1 + o_d(1))d, Glauber dynamics mixes in polynomial time with high probability over 𝒢(n, d/n) for all sufficiently large integer n. This improves the previous bound q = (α^* + o_d(1))d where α^* = 1.7632... is the unique solution of x = exp(1/x) on [1, ∞) by Efthymiou, Hayes, Štefankovič, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold on infinite regular trees. Our proof has three main ingredients. First we establish logarithmic bounds on the spectral and coupling independence constants of the Gibbs distribution by extending the tree analysis of Chen, Liu, Mani, and Moitra (J. ACM, 2026). Second, we extend the entropy-factorization framework for two-spin systems on random graphs, developed by Bezáková, Galanis, Goldberg, and Štefankovič (TALG, 2024), to proper colorings by introducing a buffer around high-degree vertices. Finally, we compare the resulting heat-bath block dynamics with the single-site Glauber dynamics.
ER -