Flip Dynamics for Sampling Colorings: Improving $(11/6-\epsilon)$ Using a Simple Metric
<|reference_start|>Flip Dynamics for Sampling Colorings: Improving $(11/6-\epsilon)$ Using a Simple Metric: We present improved bounds for randomly sampling $k$-colorings of graphs with maximum degree $\Delta$; 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\Delta$ where $\Delta$ is the maximum degree of the input graph. This bound was improved by Vigoda (1999) to $k > (11/6)\Delta$ 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 - \epsilon ) \Delta$ where $\epsilon \approx 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 $k \geq 1.809 \Delta$. This yields, through recent spectral independence results, an optimal $O(n\log{n})$ mixing time for the Glauber dynamics for the same range of $k/\Delta$ when $\Delta=O(1)$. Our proof utilizes path coupling with a simple weighted Hamming distance for "unblocked" neighbors.<|reference_end|>
@article{carlson2024flip,
    title={Flip Dynamics for Sampling Colorings: Improving $(11/6-\epsilon)$ Using
  a Simple Metric},
    author={Charlie Carlson and Eric Vigoda},
    journal={arXiv preprint arXiv:2407.04870},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04870},
    primaryClass={cs.DM}
}