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(nlogn) 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(nlogn) for the flip dynamics when k ≥ 1.809 Δ. This yields, through recent spectral independence results, an optimal O(nlogn) mixing time for the Glauber dynamics for the same range of k/Δ when Δ=O(1). Our proof utilizes path coupling with a simple weighted Hamming distance for "unblocked" neighbors.