An extension of path coupling and its application to the Glauber dynamics for graph colorings

A new method for analyzing the mixing time of Markov chains is described. This method is an extension of path coupling and involves analyzing the coupling over multiple steps. The expected behavior of the coupling at a certain stopping time is used to bound the expected behavior of the coupling after a fixed number of steps. The new method is applied to analyze the mixing time of the Glauber dynamics for graph colorings. We show that the Glauber dynamics has O(n log(n)) mixing time for triangle-free Delta -regular graphs if k colors are used, where k greater than or equal to (2 - eta)Delta, for some small positive constant eta. This is the rst proof of an optimal upper bound for the mixing time of the Glauber dynamics for some values of k in the range k less than or equal to 2 Delta