Sampling Colorings on via Glauber Dynamics
En palabras de los autores
We study the mixing time of Glauber dynamics for sampling uniformly from the proper -colorings of sparse Erd\H{o}s-R\'enyi random graphs . Our main result establishes that with probability over the draw of , Glauber dynamics is rapidly mixing for every , given any fixed and any sufficiently large fixed . In particular, the surplus of colors above is sublinear and close to . The achieved color range therefore approaches the tree uniqueness threshold and improves over the previously best achievable number of colors due to Efthymiou, Hayes, Stefankovic, and Vigoda [SODA 2018]. Moreover, our mixing-time bound is , and hence almost quadratic as . Our proof is based on establishing a spectral gap for block dynamics resulting from a suitable decomposition of into blocks and singleton vertices, ensuring that every high-degree vertex is encapsulated within a block. Our main technical contribution is a novel way of establishing rapid mixing of block dynamics via an integrated Bochner-Bakry-\'{E}mery approach, which we expect to have applications beyond sampling colorings. We further devise a new block decomposition of that strengthens and simplifies similar constructions used in previous work. Finally, to compare block and Glauber dynamics, we establish a novel recursive separator decomposition of tree-like blocks, together with a coupling argument that avoids the need for nearly uniform color marginals at vertices adjacent to hubs. This comparison argument might be of independent interest.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.