Theory seminar: Please join us on Nov 11th at 10am in the Siebel 3401 where Charlie Carlson (Simons Laufer Mathematical Sciences Institute) will give a talk, “Sampling Colorings with Markov Chains”. Please see their abstract below:
Abstract: We review the history of sample random k-colorings with and without Markov chains. We also present a new result for sampling random k-colorings in graphs with maximum degree ∆; our results hold without any further assumptions on the graph and are stronger than all previous results for general graphs. This talk is based on a paper with Eric Vigoda that will appear at the Symposium on Discrete Algorithms in 2025.
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−5. In this talk 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∆. 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/∆ when ∆ = O(1). Our proof utilizes path coupling with a simple weighted Hamming distance for “unblocked” neig hbors.