TY - GEN
T1 - Random-cluster dynamics in ℤ2
T2 - 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019
AU - Blanca, Antonio
AU - Gheissari, Reza
AU - Vigoda, Eric
N1 - Publisher Copyright:
© Antonio Blanca, Reza Gheissari, and Eric Vigoda.
PY - 2019/9
Y1 - 2019/9
N2 - The random-cluster (FK) model is a key tool for the study of phase transitions and for the design of efficient Markov chain Monte Carlo (MCMC) sampling algorithms for the Ising/Potts model. It is well-known that in the high-temperature region β < βc(q) of the q-state Ising/Potts model on an n × n box Λn of the integer lattice ℤ2, spin correlations decay exponentially fast; this property holds even arbitrarily close to the boundary of Λn and uniformly over all boundary conditions. A direct consequence of this property is that the corresponding single-site update Markov chain, known as the Glauber dynamics, mixes in optimal O(n2 log n) steps on Λn for all choices of boundary conditions. We study the effect of boundary conditions on the FK-dynamics, the analogous Glauber dynamics for the random-cluster model. On Λn the random-cluster model with parameters (p, q) has a sharp phase transition at p = pc(q). Unlike the Ising/Potts model, the random-cluster model has non-local interactions which can be forced by boundary conditions: external wirings of boundary vertices of Λn. We consider the broad and natural class of boundary conditions that are realizable as a configuration on ℤ2 \ Λn. Such boundary conditions can have many macroscopic wirings and impose long-range correlations even at very high temperatures (p ≪ pc(q)). In this paper, we prove that when q > 1 and p 6= pc(q) the mixing time of the FK-dynamics is polynomial in n for every realizable boundary condition. Previously, for boundary conditions that do not carry long-range information (namely wired and free), Blanca and Sinclair (2017) had proved that the FK-dynamics in the same setting mixes in optimal O(n2 log n) time. To illustrate the difficulties introduced by general boundary conditions, we also construct a class of non-realizable boundary conditions that induce slow (stretched-exponential) convergence at high temperatures.
AB - The random-cluster (FK) model is a key tool for the study of phase transitions and for the design of efficient Markov chain Monte Carlo (MCMC) sampling algorithms for the Ising/Potts model. It is well-known that in the high-temperature region β < βc(q) of the q-state Ising/Potts model on an n × n box Λn of the integer lattice ℤ2, spin correlations decay exponentially fast; this property holds even arbitrarily close to the boundary of Λn and uniformly over all boundary conditions. A direct consequence of this property is that the corresponding single-site update Markov chain, known as the Glauber dynamics, mixes in optimal O(n2 log n) steps on Λn for all choices of boundary conditions. We study the effect of boundary conditions on the FK-dynamics, the analogous Glauber dynamics for the random-cluster model. On Λn the random-cluster model with parameters (p, q) has a sharp phase transition at p = pc(q). Unlike the Ising/Potts model, the random-cluster model has non-local interactions which can be forced by boundary conditions: external wirings of boundary vertices of Λn. We consider the broad and natural class of boundary conditions that are realizable as a configuration on ℤ2 \ Λn. Such boundary conditions can have many macroscopic wirings and impose long-range correlations even at very high temperatures (p ≪ pc(q)). In this paper, we prove that when q > 1 and p 6= pc(q) the mixing time of the FK-dynamics is polynomial in n for every realizable boundary condition. Previously, for boundary conditions that do not carry long-range information (namely wired and free), Blanca and Sinclair (2017) had proved that the FK-dynamics in the same setting mixes in optimal O(n2 log n) time. To illustrate the difficulties introduced by general boundary conditions, we also construct a class of non-realizable boundary conditions that induce slow (stretched-exponential) convergence at high temperatures.
UR - http://www.scopus.com/inward/record.url?scp=85072862550&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85072862550&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2019.67
DO - 10.4230/LIPIcs.APPROX-RANDOM.2019.67
M3 - Conference contribution
AN - SCOPUS:85072862550
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019
A2 - Achlioptas, Dimitris
A2 - Vegh, Laszlo A.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 20 September 2019 through 22 September 2019
ER -