Fall 2020

Sampling From the Random Cluster Model at All Temperatures on Random Graphs

Thursday, September 24th, 2020 9:55 am10:20 am

Add to Calendar


Will Perkins, University of Illinois at Chicago

We give efficient approximate counting and sampling algorithms for the large q random cluster and ferromagnetic Potts models on random regular graphs at all temperatures, including critical, showing that this type of phase transition is no barrier to efficient algorithms.  We also deduce probabilistic information such as the distribution of the log partition function and exponential decay of correlations conditioned on a phase.  Our techniques (using polymer models and the cluster expansion) are quite different but complementary to those based on the cavity method and the second moment method.  Joint work with Tyler Helmuth and Matthew Jenssen. 

PDF icon rcmodelpdf.pdf952.79 KB