Clayton Mizgerd (UIC)- Sampling 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.
Speakers
Clayton Mizgerd
Clayton Mizgerd is a fourth year PhD student at the University of Illinois Chicago advised by Vishesh Jain and Dhruv Mubayi. His research interests include Markov chains, random graph theory, and extremal combinatorics.
