Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local UniformityResearch Paper
Counting the proper -colorings of a graph approximately, and sampling one nearly uniformly, are equivalent problems, and both are classical test cases for Markov chain Monte Carlo. The simplest sampler is the Glauber dynamics, which recolors one vertex at a time. Jerrum (Jer95) showed that it mixes in steps whenever , where is…