Swendsen-Wang is faster than single-bond dynamics

Abstract

We prove that the spectral gap of the Swendsen-Wang dynamics for the random-cluster model is larger than the spectral gap of a single-bond dynamics, that updates only a single edge per step. For this we give a representation of the algorithms on the joint (Potts/random-cluster) model. Furthermore we obtain upper and lower bounds on the mixing time of the single-bond dynamics on the discrete $d$-dimensional torus of side length $L$ at the Potts transition temperature for $q$ large enough that are exponential in $L^{d-1}$, complementing a result of Borgs, Chayes and Tetali.

17 pages

References in corpus (2)

• Comparison of Swendsen-Wang and Heat-Bath Dynamics
• Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point

Cited by in corpus (8)

• Hit-and-run for numerical integration
• The worm process for the Ising model is rapidly mixing
• Metastability of the Potts ferromagnet on random regular graphs
• Dynamics for the mean-field random-cluster model
• The Critical Mean-field Chayes-Machta Dynamics
• Random-Cluster Dynamics in ${\mathbb{Z}}^2$
• Information Percolation and Cutoff for the Random-Cluster Model
• Spatial Mixing and Systematic Scan Markov chains