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 structural 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 two-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 -5 . 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 ∆ ≥ 125 and k ≥ 1.809∆. This yields, through recent spectral independence results, an optimal O(n log n) mixing time for the Glauber dynamics for every fixed ∆ ≥ 125 in the same range of k/∆. Our proof utilizes path coupling with a simple weighted Hamming distance for "unblocked" neighbors.