文章基本信息

标题：Dynamics for the Mean-field Random-cluster Model
本地全文：下载
作者：Antonio Blanca ; Alistair Sinclair
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：40
页码：528-543
DOI：10.4230/LIPIcs.APPROX-RANDOM.2015.528
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：random-cluster model; random graphs; Markov chains; statistical physics; dynamics