Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
Vishesh Jain, Clayton Mizgerd, Eric Vigoda · 2026
Read Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity by Vishesh Jain, Clayton Mizgerd, Eric Vigoda (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-11938.txt.
Introduction
Jain, Mizgerd, and Vigoda study how fast a simple local chain samples proper colorings of a graph when colors only slightly outnumber the maximum degree. They prove optimal mixing for graphs of girth at least seven once colors exceed the degree by any fixed fraction, building on a non-Markovian coupling where updates may reach into future steps. New local uniformity results carry the argument down to constant degree.
Catalog record
| CREATOR | Vishesh Jain, Clayton Mizgerd, Eric Vigoda |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 215425 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.11938