Fast and slow mixing of Markov chains for the ferromagnetic Potts model

Abstract:

The Potts model is a statistical physics model of magnetism closely related to the Tutte polynomial of a graph.  The state space is the set of all maps from the vertex set of a graph to a finite set of spins (also called colours, or labels). In the ferromagnetic model, spin configurations where many edges are monochromatic receive higher weight.

The simplest Markov chain for sampling states from the Potts model is the Glauber dynamics, which updates the spin of a single vertex of the underlying graph at each step.  The stationary distribution of the Glauber dynamics is the Gibbs distribution, and classical Markov chain theory says that if left to run forever, eventually the Glauber dynamics will sample precisely from the Gibbs distribution.  However, this convergence to stationarity can be fast (polynomial time) or slow (exponential time).

I will review some results obtained with Magnus Bordewich (Durham) and Viresh Patel (Queen Mary), investigating the mixing time of the Glauber dynamics for graphs with bounded maximum degree. In particular, we showed the existence of a range of parameters such that, when there are sufficiently many spins (colours), the Glauber dynamics mixes rapidly for the toroidal grid, but mixes slowly for almost all 4-regular graphs.