![Counting Complexity and Phase Transitions_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Counting%20Complexity%20and%20Phase%20Transitions_hi-res.jpg?h=bf33d09a&itok=MrH5eN5T)
Abstract
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.