Sampling Colorings with Flip Dynamics

Zoom Link

This talk examines the problem of sampling proper 𝑘-colorings from the uniform distribution using Markov chains. The Glauber dynamics, a simple single-site update Markov chain, was shown by Jerrum (1995) to achieve an optimal mixing time of 𝑂(𝑛log(𝑛)) when the number of colors 𝑘 > 2Δ, where Δ is the maximum degree of the graph being colored. In 1999, Vigoda introduced flip dynamics, a generalization of Glauber dynamics, and demonstrated that it has optimal mixing time when 𝑘>11/6Δ. This result remained the best known for general graphs for 20 years until Chen et al. (2019) established optimal mixing of flip dynamics when 𝑘 > (11/6 − 𝜖), where 𝜖 is approximately 10^(-5). Recently, Carlson and Vigoda (2024) provided the first substantial improvement over these results by proving an optimal mixing time for flip dynamics when 𝑘 ≥ 1.809 Δ. Their proof employs a path coupling argument with a simple weighted Hamming distance for "unblocked" neighbors. In this talk, we review the problem of sampling proper colorings, the development of flip dynamics, and the tools used in the aforementioned results

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.