Rapid mixing of Glauber dynamics for colorings below Vigoda's $11/6$ threshold
Abstract
A wellknown 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 $\Delta$ is rapidly mixing for $k \geq \Delta +2$. In FOCS 1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameters on the set of proper $k$colorings for $k > \frac{11}{6}\Delta$, implying rapid mixing for Glauber dynamics. In this paper, we obtain the first improvement beyond the $\frac{11}{6}\Delta$ barrier for general graphs by showing rapid mixing for $k > (\frac{11}{6}  \eta)\Delta$ for some positive constant $\eta$. 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.
 Publication:

arXiv eprints
 Pub Date:
 April 2018
 arXiv:
 arXiv:1804.04025
 Bibcode:
 2018arXiv180404025D
 Keywords:

 Computer Science  Discrete Mathematics;
 Computer Science  Data Structures and Algorithms;
 Mathematics  Combinatorics;
 Mathematics  Probability
 EPrint:
 21 pages