Galanis, Andreas ;
Štefankovic, Daniel ;
Vigoda, Eric
SwendsenWang Algorithm on the MeanField Potts Model
Abstract
We study the qstate ferromagnetic Potts model on the nvertex complete graph known as the meanfield (CurieWeiss) model. We analyze the SwendsenWang 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 singlesite Glauber dynamics. The case q=2 (the SwendsenWang algorithm for the ferromagnetic Ising model) undergoes a slowdown at the uniqueness/nonuniqueness critical temperature for the infinite Deltaregular tree (Long et al., 2014) but yet still has polynomial mixing time at all (inverse) temperatures beta>0 (Cooper et al., 2000). In contrast for q>=3 there are two critical temperatures 0<beta_u<beta_rc that are relevant, these two critical points relate to phase transitions in the infinite tree. We prove that the mixing time of the SwendsenWang algorithm for the ferromagnetic Potts model on the nvertex complete graph satisfies: (i) O(log n) for beta<beta_u, (ii) O(n^(1/3)) for beta=beta_u, (iii) exp(n^(Omega(1))) for beta_u<beta<beta_rc, and (iv) O(log n) for beta>=beta_rc. These results complement refined results of Cuff et al. (2012) on the mixing time of the Glauber dynamics for the ferromagnetic Potts model. The most interesting aspect of our analysis is at the critical temperature beta=beta_u, which requires a delicate choice of a potential function to balance the conflating factors for the slow drift away from a fixed point (which is repulsive but not Jacobian repulsive): close to the fixed point the variance from the percolation step dominates and sufficiently far from the fixed point the dynamics of the size of the dominant color class takes over.
BibTeX  Entry
@InProceedings{galanis_et_al:LIPIcs:2015:5338,
author = {Andreas Galanis and Daniel {\v{S}}tefankovic and Eric Vigoda},
title = {{SwendsenWang Algorithm on the MeanField Potts Model}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {815828},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5338},
URN = {urn:nbn:de:0030drops53389},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.815},
annote = {Keywords: Ferromagnetic Potts model, SwendsenWang dynamics, mixing time, meanfield analysis, phase transition.}
}
13.08.2015
Keywords: 

Ferromagnetic Potts model, SwendsenWang dynamics, mixing time, meanfield analysis, phase transition. 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Issue date: 

2015 
Date of publication: 

13.08.2015 