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

CREATORVishesh Jain, Clayton Mizgerd, Eric Vigoda
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE215425
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.11938

Browse the full library · About the Tower of Babel