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 | |
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/Territory | Spain |
City | Barcelona |
Period | 16/01/17 → 19/01/17 |
Internet address |