Title: Sampling q-colorings on bounded degree graphs
Abstract: A seminal conjecture of Jerrum states that the Glauber dynamics on q-colorings of a graph mix rapidly whenever $q \geq \Delta+2$. We will discuss the history of this problem and the partial progress before showing a new result that $q > (1+o(1))\Delta$ suffices for optimal mixing time guarantees on graphs of girth at least 11.
We will briefly describe the techniques involved. First is a more careful treatment of the non-Markovian coupling of Hayes and Vigoda. We then prove a local uniformity result for the Metropolis dynamics. Finally, we are able to get rapid mixing from an arbitrary start using these tools. Based on joint work with Vishesh Jain and Eric Vigoda.
Reza Gheissari
Email