Flip Dynamics for Sampling Colorings: Improving (11/6 − ε) Using A Simple Metric

We present improved bounds for randomly sampling k-colorings of graphs with maximum degree ∆; our results hold without any further assumptions on the graph. The Glauber dynamics is a simple single-site update Markov chain. Jerrum (1995) proved an optimal O(n log n) mixing time bound for Glauber dynamics whenever k > 2∆ where ∆ is the maximum degree of the input graph. This bound was improved by Vigoda (1999) to k > (11/6)∆ using a “flip” dynamics which recolors (small) maximal 2-colored components in each step. Vigoda’s result was the best known for general graphs for 20 years until Chen et al. (2019) established optimal mixing of the flip dynamics for k > (11/6 − ε)∆ where ε ≈ 10⁻⁵. We present the first substantial improvement over these results. We prove an optimal mixing time bound of O(n log n) for the flip dynamics when k ≥ 1.809∆. Our proof utilizes path coupling with a simple weighted Hamming distance for “unblocked” neighbors.