Videos

Connections Workshop: Probability and Statistics of Discrete Structures: Sampling Colorings with Flip Dynamics

Presenter
January 24, 2025
Keywords:
  • random graphs
  • network inference
  • phase transitions
  • probabilistic combinatorics
  • Markov Chain Monte Carlo
MSC:
  • 05C80 - Random graphs (graph-theoretic aspects)
Abstract
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.