Title: Rapid mixing of Glauber dynamics for colorings below Vigoda’s 11/6 threshold
| Speaker: | Michelle Delcourt |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
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 1999 Vigoda showed rapid mixing time of a modified version of flip dynamics for k > 11/6Δ , implying polynomial time mixing for Glauber dynamics under the same constraints. This conjecture has attracted a lot of attention in the literature and better results are known for certain classes of graphs. In this talk, we improve Vigoda's bound for general graphs by showing that there exists a constant η > 0 such that the Glauber dynamics mixes in polynomial time for k ≥ (11/6-η)Δ. Our proof combines path coupling with a new kind of metric we introduce to incorporate a count of the extremal configurations of the chain. This "extremal" metric proves to be much easier to analyze than stopping-time-based metrics, and hence we believe will have fruitful applications for bounding the mixing times of other Markov chains.
This is joint work with Guillem Perarnau and Luke Postle.