TY - GEN
T1 - Dynamics for the mean-field random-cluster model
AU - Blanca, Antonio
AU - Sinclair, Alistair
N1 - Publisher Copyright:
© Antonio Blanca and Alistair Sinclair.
PY - 2015/8/1
Y1 - 2015/8/1
N2 - The random-cluster model has been widely studied as a unifying framework for random graphs, spin systems and random spanning trees, but its dynamics have so far largely resisted analysis. In this paper we study a natural non-local Markov chain known as the Chayes-Machta dynamics for the mean-field case of the random-cluster model, and identify a critical regime (λs, λS) of the model parameter λ in which the dynamics undergoes an exponential slowdown. Namely, we prove that the mixing time is θ(log n) if ∉ 62 [λs, λS], and exp((p n)) when λ ∈ (λs, λS). These results hold for all values of the second model parameter q > 1. In addition, we prove that the local heat-bath dynamics undergoes a similar exponential slowdown in (λs, λS).
AB - The random-cluster model has been widely studied as a unifying framework for random graphs, spin systems and random spanning trees, but its dynamics have so far largely resisted analysis. In this paper we study a natural non-local Markov chain known as the Chayes-Machta dynamics for the mean-field case of the random-cluster model, and identify a critical regime (λs, λS) of the model parameter λ in which the dynamics undergoes an exponential slowdown. Namely, we prove that the mixing time is θ(log n) if ∉ 62 [λs, λS], and exp((p n)) when λ ∈ (λs, λS). These results hold for all values of the second model parameter q > 1. In addition, we prove that the local heat-bath dynamics undergoes a similar exponential slowdown in (λs, λS).
UR - http://www.scopus.com/inward/record.url?scp=84958543688&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958543688&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2015.528
DO - 10.4230/LIPIcs.APPROX-RANDOM.2015.528
M3 - Conference contribution
AN - SCOPUS:84958543688
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 528
EP - 543
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
A2 - Garg, Naveen
A2 - Jansen, Klaus
A2 - Rao, Anup
A2 - Rolim, Jose D. P.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015
Y2 - 24 August 2015 through 26 August 2015
ER -