Comparison of Swendsen‐Wang and heat‐bath dynamics1. Issue 4 (11th May 2012)

• Record Type: Journal Article
• Authors: Ullrich, Mario
• Is Part Of: Random structures & algorithms. Volume 42:Issue 4(2013)
• Page Start: 520
• Page End: 535
• Publication Date: 2012-05-11
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20431
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We prove that the spectral gap of the Swendsen‐Wang process for the Potts model on graphs with bounded degree is bounded from below by some constant times the spectral gap of any single‐spin dynamics. This implies rapid mixing for the two‐dimensional Potts model at all temperatures above the critical one, as well as rapid mixing at the critical temperature for the Ising model. After this we introduce a modified version of the Swendsen‐Wang algorithm for planar graphs and prove rapid mixing for the two‐dimensional Potts models at all non‐critical temperatures. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 520–535, 2013</p> </abstract>