Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
We study the mixing time of the single-site Glauber dynamics for sampling proper \(q\)-colorings on sparse Erdős-Rényi random graphs \(\mathcal{G}(n, d/n)\). We prove that, whenever \(q \ge (1 + o_d(1))d\), Glauber dynamics mixes in polynomial time with high probability over \(\mathcal{G}(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, \infty)\) by Efthymiou, Hayes, Štefankovič, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.25391
curl -X POST /api/v1/records/arxiv/2610.25391/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.25391/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'