pipette
ENEnglish

Sampling Colorings on via Glauber Dynamics

Leon Schiller

Preprint

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.