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 (nn) 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^-5. We present the first substantial improvement over these results. We prove an optimal mixing time bound of O (nn) for the flip dynamics when k 1. 809. This yields, through recent spectral independence results, an optimal O (nn) 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.