Rapid mixing of Glauber dynamics for colorings below Vigoda's 11/6 threshold
share
A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of k-colorings of a graph G on n vertices with maximum degree Δ is rapidly mixing for k ≥Δ +2. In FOCS 1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameters on the set of proper k-colorings for k > 11/6Δ, implying rapid mixing for Glauber dynamics. In this paper, we obtain the first improvement beyond the 11/6Δ barrier for general graphs by showing rapid mixing for k > (11/6 - η)Δ for some positive constant η. The key to our proof is combining path coupling with a new kind of metric that incorporates a count of the extremal configurations of the chain. Additionally, our results extend to list coloring, a widely studied generalization of coloring. Combined, these results answer two open questions from Frieze and Vigoda's 2007 survey paper on Glauber dynamics for colorings.
READ FULL TEXT