Random Cluster Dynamics for the Ising Model is Rapidly Mixing

Heng Guo; Mark Jerrum

doi:10.1137/1.9781611974782.118

Random Cluster Dynamics for the Ising Model is Rapidly Mixing

Heng Guo, Mark Jerrum

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 on an arbitrary n- vertex graph is bounded by a polynomial in n. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature also has a polynomial mixing time bound.

Original language	English
Title of host publication	Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher	Society for Industrial and Applied Mathematics
Pages	1818-1827
Number of pages	10
Volume	28
Edition	2
ISBN (Electronic)	978-1-61197-478-2
DOIs	https://doi.org/10.1137/1.9781611974782.118
Publication status	E-pub ahead of print - 19 Jan 2017
Event	Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms - Hotel Porta Fira, Barcelona, Spain Duration: 16 Jan 2017 → 19 Jan 2017 http://www.siam.org/meetings/da17/

Conference

Conference	Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Abbreviated title	SIAM 2017
Country	Spain
City	Barcelona
Period	16/01/17 → 19/01/17
Internet address	http://www.siam.org/meetings/da17/

Access to Document

10.1137/1.9781611974782.118Licence: Creative Commons: Attribution (CC-BY)

IsingRC-AAPAccepted author manuscript, 188 KBLicence: Creative Commons: Attribution (CC-BY)

http://epubs.siam.org/doi/abs/10.1137/1.9781611974782.118Licence: Creative Commons: Attribution (CC-BY)

Fingerprint Dive into the research topics of 'Random Cluster Dynamics for the Ising Model is Rapidly Mixing'. Together they form a unique fingerprint.

Cite this

@inproceedings{0f0a80fe4ac84afe87cb1257bf7c27a8,

title = "Random Cluster Dynamics for the Ising Model is Rapidly Mixing",

abstract = "We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 on an arbitrary n- vertex graph is bounded by a polynomial in n. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature also has a polynomial mixing time bound.",

author = "Heng Guo and Mark Jerrum",

year = "2017",

month = jan,

day = "19",

doi = "10.1137/1.9781611974782.118",

language = "English",

volume = "28",

pages = "1818--1827",

booktitle = "Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Society for Industrial and Applied Mathematics",

edition = "2",

note = "Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM 2017 ; Conference date: 16-01-2017 Through 19-01-2017",

url = "http://www.siam.org/meetings/da17/",

}

Guo, H & Jerrum, M 2017, Random Cluster Dynamics for the Ising Model is Rapidly Mixing. in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. 2 edn, vol. 28, Society for Industrial and Applied Mathematics, pp. 1818-1827, Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16/01/17. https://doi.org/10.1137/1.9781611974782.118

TY - GEN

T1 - Random Cluster Dynamics for the Ising Model is Rapidly Mixing

AU - Guo, Heng

AU - Jerrum, Mark

PY - 2017/1/19

Y1 - 2017/1/19

N2 - We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 on an arbitrary n- vertex graph is bounded by a polynomial in n. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature also has a polynomial mixing time bound.

AB - We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 on an arbitrary n- vertex graph is bounded by a polynomial in n. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature also has a polynomial mixing time bound.

U2 - 10.1137/1.9781611974782.118

DO - 10.1137/1.9781611974782.118

M3 - Conference contribution

VL - 28

SP - 1818

EP - 1827

BT - Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Society for Industrial and Applied Mathematics

T2 - Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 16 January 2017 through 19 January 2017

ER -