Sampling Colorings on $G(n, d/n)$ via Glauber Dynamics
Source: arxiv.org/abs/2611.12444
We study the mixing time of Glauber dynamics for sampling uniformly from the proper $q$-colorings of sparse Erdős-Rényi random graphs $G(n,d/n)$. Our main result establishes that with probability $1-o(1)$ over the draw of $G$, Glauber dynamics is rapidly mixing for every $q\geq d+d^{1/2+\varepsilon}$, given any fixed $0 1.763 d$ due to Efthymiou, Hayes, Stefankovic, and Vigoda [SODA 2018]. Moreover, our mixing-time bound is $O(n^{2+o_d(1)})$, and hence almost quadratic as $d\rightarrow\infty$. Our proof is based on establishing a spectral gap for block dynamics resulting from a suitable…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.12444
curl -X POST /api/v1/records/arxiv/2611.12444/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.12444/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'