{"id":"arxiv/2611.12444","url":"https://arxiv.org/abs/2611.12444","tags":["math.CO","cs.DS","math.PR"],"score":0,"title":"Sampling Colorings on $G(n, d/n)$ via Glauber Dynamics","domain":"math.CO","source":"arxiv","authors":["Leon Schiller"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-09","reactions":{}}