2026-07-22T13:39:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5322 2024-03-06T10:36:19Z ddc:004 open_access

Dynamics for the Mean-field Random-cluster Model Blanca, Antonio Sinclair, Alistair random-cluster model random graphs Markov chains statistical physics dynamics 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 (lambda_s,lambda_S) of the model parameter lambda in which the dynamics undergoes an exponential slowdown. Namely, we prove that the mixing time is Theta(log n) if lambda is not in [lambda_s,lambda_S], and e^Omega(sqrt{n}) when lambda is in (lambda_s,lambda_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 (lambda_s,lambda_S). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antonio Blanca and Alistair Sinclair 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.528 urn:nbn:de:0030-drops-53227 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.528 eng https://creativecommons.org/licenses/by/3.0/legalcode