Theory of Computing Seminar

Friday May 29, 2015 12:00 PM

Dynamics for the random-cluster model

Speaker: Alistair Sinclair, EECS, UC Berkeley/Simons Institute
Location: Annenberg 213

The random-cluster model is a unifying framework for studying random graphs, spin systems in physics and random spanning trees.  The model is closely related to, though much more general than the classical Ising and Potts models, but its dynamics are much less well understood.  In this talk we study a natural non-local Markov chain known as the Chayes-Machta dynamics for the mean-field case of the random-cluster model, and identify a critical interval $(lambda_s,lambda_S)$ of the model parameter $lambda$ in which the dynamics undergoes an exponential slowdown.  Namely, we prove that the mixing time is $Theta(log n)$ for $lambda$ outside the above interval, and $exp(Omega(sqrt{n}))$ for $lambda$ inside the interval.  These results hold for all values of the second model parameter $q>1$.  Thus, we obtain the first analysis of a dynamics for the random-cluster model for values of $q$ other than the already well understood special case $q=2$ (which corresponds to the Ising model) over almost the full range of values of $lambda$.  In addition, we prove that the local heat-bath dynamics undergoes a similar exponential slowdown in $(lambda_s,lambda_S)$.

This is joint work with Antonio Blanca.

Contact: Thomas Vidick vidick@cms.caltech.edu