| The Glauber dynamics is a simple Markov chain widely used in a variety of fields for randomly sampling from probability distributions defined on large sets of combinatorial structures. We analyze the convergence properties of the Glauber dynamics for randomly sampling k-colorings of a graph on n vertices with maximum degree Δ.; The outstanding conjecture in the area is that the Glauber dynamics converges to its stationary distribution in polynomial time whenever k ≥ Δ + 2. The question is of interest not only for its combinatorial appeal, but also because the Glauber dynamics forms the basis for the best known randomized approximation algorithm for counting k-colorings, a #P-complete problem. The question is also of interest in Statistical Physics, for its connection to the existence of phase transitions in Gibbs distributions.; Prior to our work, the best general results were that the Glauber dynamics converges in time O(n2 log n) for k > 11/6Δ and in time O(n log n) for k > (2–10−12 )Δ. Assuming Δ = Ω(log n) and girth = Ω(log Δ), it was recently shown that the Glauber dynamics converges in time O(n log n) for k > β*Δ, where β* ≈ 1.498.; Our main result is that the Glauber dynamics converges in time O(n log n) for k > (1 + &epsis;)Δ, assuming Δ = Ω(log n) and girth ≥ 11. Our best result under the weaker hypotheses that Δ = Ω(1) and girth ≥ 5 is that the convergence time is O(n log n) for k > α*Δ, where α* ≈ 1.763.; Some of our tools and techniques may be of independent interest. Our main result relies on the explicit construction and analysis of a non-Markovian coupling; this is the first time a non-Markovian coupling has been used to solve an open problem. Our reductions of the girth requirements rely on a general technique for analyzing multilinear functions of conditionally independent random variables. We present a generalization of the Path Coupling Theorem which simplifies the construction and analysis of variable-length couplings. |
