School Seminars and Colloquia

Asymptotic mixing times of the Swendsen-Wang process for the Potts model on the complete graph

Discrete Structures and Algorithms (Seminar)

by Tim Garoni


Institution: Monash University
Date: Wed 22nd May 2013
Time: 2:30 PM
Location: Old Geology Lecture Theatre 2

Abstract: The Potts model is a natural generalization of the well-known Ising model of statistical mechanics, and is intimately related to the Tutte polynomial in algebraic graph theory. The Swendsen-Wang process is a finite Markov chain which has revolutionized the way in which Monte Carlo studies of the Potts model, and many related models, are performed. We will discuss the Swendsen-Wang process for the Potts model with $q \ge 3$ states on the complete graph on $n$ vertices, and obtain the large $n$ asymptotics of the mixing time as a function of temperature. The mixing time is exponentially large in $n$ throughout a non-trivial neighbourhood of the equilibrium transition temperature. Strictly outside this neighbourhood, in the high and low temperature regimes, the mixing time is $O(\log n)$, while at the left boundary it exhibits the non-trivial power-law scaling $\Theta(n^{1/3})$. We will sketch the proof of this result, and (time permitting) discuss how our results might be extended to study mixing times of related processes. No prior knowledge of statistical mechanics will be assumed.