Glauber Dynamics is a well studied Markov Chain to sample k-colorings of a graph. However, a basic coupling/path coupling analysis of Glauber Dynamics requires for the chain to be rapid mixing. However, it is hypothesized (and intuitive) that the chain should be rapid mixing for any . Bringing this gap down is a popular open problem. Jerrum used an extremely clever coupling to bring it down to .
Vigoda takes a totally different approach. He defines a completely new Markov Chain called Flip Dynamics and proves that it is rapid mixing under the condition that . He then makes use of a comparison theorem, courtesy Diaconis and Saloff-Coste, to then prove that Glauber Dynamics is also rapid mixing.
Here are the notes I took while reading his wonderful paper. Unlike my other posts these notes aren’t of very high quality. However I decided to put them here as a placeholder while I find the time to refine them into a proper blog post.