Mixing of the Glauber dynamics for the ferromagnetic Potts model1. Issue 1 (4th September 2014)

• Record Type: Journal Article
• Authors: Bordewich, Magnus; Greenhill, Catherine; Patel, Viresh
• Is Part Of: Random structures & algorithms. Volume 48:Issue 1(2016)
• Page Start: 21
• Page End: 52
• Publication Date: 2014-09-04
• Subjects: Glauber dynamics -- mixing time -- Potts model -- ferromagnetic; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20569
• Languages: English
• ISSNs: 1042-9832

Abstract

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