Mixing of the Glauber dynamics for the ferromagnetic Potts model1. Issue 1 (4th September 2014) - Bordewich, Magnus; Greenhill, Catherine; Patel, Viresh
Abstract: We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree (Δ) of the underlying graph and the number of colours or spins ( q ) in determining whether the dynamics mixes rapidly or not. We find a lower bound L on the number of colours such that Glauber dynamics is rapidly mixing if at least L colours are used. We give a closely‐matching upper bound U on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random Δ‐regular graphs when at most U colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree Δ, e.g. toroidal grids for Δ = 4. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 21–52, 2016