Presented on October 2, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116E.
For all other @math , Glauber dynamics for the Potts model on @math is again known to have @math for all @math by combining the following results: Alexander @cite_22 related exponential decay of connection probabilities in the FK model on @math to an analogous spatial mixing property in the Potts model on a finite box; Beffara and Duminil-Copin @cite_38 proved the exponential decay of correlations in the FK model for all @math ; and the works of Martinelli @cite_42 @cite_45 @cite_40 translate the aforementioned spatial mixing property to an @math bound on the inverse gap. In contrast, Potts Glauber dynamics on @math is always expected to be exponentially slow for @math : as mentioned before, this is known for @math , and was proved for large enough @math in @cite_8 @cite_17 .
@cite_38 @cite_22 @cite_8 @cite_42 @cite_40 @cite_45 @cite_17
2126692288 1980404829 1982190141 2004724832
Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z sup d . We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L sup d-1 . In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point. We prove comparison results for the Swendsen-Wang (SW) dynamics, the heat-bath (HB) dynamics for the Potts model and the single-bond (SB) dynamics for the random-cluster model on arbitrary graphs. In particular, we prove that rapid mixing of HB implies rapid mixing of SW on graphs with bounded maximum degree and that rapid mixing of SW and rapid mixing of SB are equivalent. Additionally, the spectral gap of SW and SB on planar graphs is bounded from above and from below by the spectral gap of these dynamics on the corresponding dual graph with suitably changed temperature. As a consequence we obtain rapid mixing of the Swendsen-Wang dynamics for the Potts model on the two-dimensional square lattice at all non-critical temperatures as well as rapid mixing for the two-dimensional Ising model at all temperatures. Furthermore, we obtain new results for general graphs at high or low enough temperatures. We prove that the spectral gap of the Swendsen-Wang process for the Potts model on graphs with bounded degree is bounded from below by some constant times the spectral gap of any single-spin dynamics. This implies rapid mixing for the two-dimensional Potts model at all temperatures above the critical one, as well as rapid mixing at the critical temperature for the Ising model. After this we introduce a modified version of the Swendsen-Wang algorithm for planar graphs and prove rapid mixing for the two-dimensional Potts models at all non-critical temperatures. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 520–535, 2013 Consider the problem of approximately counting weighted independent sets of a graph G with activity λ, i.e., where the weight of an independent set I is λ|I|. We present a novel analysis yielding a deterministic approximation scheme which runs in polynomial time for any graph of maximum degree Δ and λ< λc=(Δ-1)Δ-1 (Δ-2)Δ. This improves on the previously known general bound of λ ≤ (2 ‾ Δ-2). The new regime includes the interesting case of λ=1 (uniform weights) and Δ ≤ 5. The previous bound required Δ ≤ 4 for uniform approximate counting and there is evidence that for Δ ≥ 6 the problem is hard. Note that λc is the critical activity for uniqueness of the Gibbs measure on the regular tree of degree Δ, i.e., for λ ≤ λc the probability that the root is in the independent set is asymptotically independent of the configuration on the leaves far below. Indeed, our analysis is focused on establishing decay of correlations with distance in the above weighted distribution. We show that on any graph of maximum degree Δ correlations decay with distance at least as fast as they do on the regular tree of the same degree. This resolves an open conjecture in statistical physics. Our comparison of a general graph with the tree uses an algorithmic argument yielding the approximation scheme mentioned above. Also, by existing arguments, establishing decay of correlations for all graphs and λ<λc gives that the Glauber dynamics is rapidly mixing in this regime. However, the implication from decay of correlations to rapid mixing of the dynamics is only known to hold for graphs of subexponential growth, and hence, our result regarding the Glauber dynamics is limited to this class of graphs.