####
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\geq (2-\eta)\Delta$, for some small positive constant
$\eta$. This is the first proof of an optimal upper bound for the
mixing time of the Glauber dynamics for some values of k in the range
$k\leq 2\Delta$.