How difficult is it to sample configurations of a spin model on Delta-regular graphs? Do Markov chains mix rapidly on random Delta-regular graphs?

Mean-field models provide a simplification that can lead to (qualitative) insights on the above questions. We study the q-state ferromagnetic Potts model on the n-vertex complete graph known as the mean-field (Curie-Weiss) model and analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics.

Joint work with Andreas Galainis and Eric Vigoda.