skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Thursday, May 23 until 2:00 AM ET on Friday, May 24 due to maintenance. We apologize for the inconvenience.


Title: Metastability of the Potts Ferromagnet on Random Regular Graphs
Abstract

We study the performance of Markov chains for theq-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis and, in fact, even analysing the properties of the Potts distribution has remained elusive. It is conjectured that the performance of Markov chains is dictated by metastability phenomena, i.e., the presence of “phases” (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape, and therefore cause slow mixing. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task. Our first contribution is to detail the emergence of the two relevant phases for theq-state Potts model on thed-regular random graph for all integers$$q,d\ge 3$$q,d3, and establish that for an interval of temperatures, delineated by the uniqueness and a broadcasting threshold on thed-regular tree, the two phases coexist (as possible metastable states). The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. This significantly refines earlier results by Helmuth, Jenssen, and Perkins who had established phase coexistence for a small interval around the so-called ordered-disordered threshold (via different arguments) that applied for largeqand$$d\ge 5$$d5. Based on our new structural understanding of the model, our second contribution is to obtain metastability results for two classical Markov chains for the Potts model. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, by showing an exponential lower bound on the mixing time above the uniqueness threshold. Then, we obtain tight results even for the non-local and more elaborate Swendsen–Wang chain, where we establish slow mixing/metastability for the whole interval of temperatures where the chain is conjectured to mix slowly on the random regular graph. The key is to bound the conductance of the chains using a random graph “planting” argument combined with delicate bounds on random-graph percolation.

 
more » « less
NSF-PAR ID:
10396273
Author(s) / Creator(s):
; ; ; ; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Communications in Mathematical Physics
Volume:
401
Issue:
1
ISSN:
0010-3616
Format(s):
Medium: X Size: p. 185-225
Size(s):
["p. 185-225"]
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    We establish rapid mixing of the random-cluster Glauber dynamics on random$$\varDelta $$Δ-regular graphs for all$$q\ge 1$$q1and$$pp<pu(q,Δ), where the threshold$$p_u(q,\varDelta )$$pu(q,Δ)corresponds to a uniqueness/non-uniqueness phase transition for the random-cluster model on the (infinite)$$\varDelta $$Δ-regular tree. It is expected that this threshold is sharp, and for$$q>2$$q>2the Glauber dynamics on random$$\varDelta $$Δ-regular graphs undergoes an exponential slowdown at$$p_u(q,\varDelta )$$pu(q,Δ). More precisely, we show that for every$$q\ge 1$$q1,$$\varDelta \ge 3$$Δ3, and$$pp<pu(q,Δ), with probability$$1-o(1)$$1-o(1)over the choice of a random$$\varDelta $$Δ-regular graph onnvertices, the Glauber dynamics for the random-cluster model has$$\varTheta (n \log n)$$Θ(nlogn)mixing time. As a corollary, we deduce fast mixing of the Swendsen–Wang dynamics for the Potts model on random$$\varDelta $$Δ-regular graphs for every$$q\ge 2$$q2, in the tree uniqueness region. Our proof relies on a sharp bound on the “shattering time”, i.e., the number of steps required to break up any configuration into$$O(\log n)$$O(logn)sized clusters. This is established by analyzing a delicate and novel iterative scheme to simultaneously reveal the underlying random graph with clusters of the Glauber dynamics configuration on it, at a given time.

     
    more » « less
  2. We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis and, in fact, even analysing the properties of the Potts distribution has remained elusive. It is conjectured that the performance of Markov chains is dictated by metastability phenomena, i.e., the presence of "phases" (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape, and therefore cause slow mixing. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task. Our first contribution is to detail the emergence of the metastable phases for the q-state Potts model on the d-regular random graph for all integers q,d ≥ 3, and establish that for an interval of temperatures, delineated by the uniqueness and a broadcasting threshold on the d-regular tree, the two phases coexist. The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. This significantly refines earlier results by Helmuth, Jenssen, and Perkins who had established phase coexistence for a small interval around the so-called ordered-disordered threshold (via different arguments) that applied for large q and d ≥ 5. Based on our new structural understanding of the model, we obtain various algorithmic consequences. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, showing an exponential lower bound on the mixing time above the uniqueness threshold. Then, we obtain tight results even for the non-local and more elaborate Swendsen-Wang chain, where we establish slow mixing/metastability for the whole interval of temperatures where the chain is conjectured to mix slowly on the random regular graph. The key is to bound the conductance of the chains using a random graph "planting" argument combined with delicate bounds on random-graph percolation. 
    more » « less
  3. Abstract

    We study the structure of the Liouville quantum gravity (LQG) surfaces that are cut out as one explores a conformal loop-ensemble$$\hbox {CLE}_{\kappa '}$$CLEκfor$$\kappa '$$κin (4, 8) that is drawn on an independent$$\gamma $$γ-LQG surface for$$\gamma ^2=16/\kappa '$$γ2=16/κ. The results are similar in flavor to the ones from our companion paper dealing with$$\hbox {CLE}_{\kappa }$$CLEκfor$$\kappa $$κin (8/3, 4), where the loops of the CLE are disjoint and simple. In particular, we encode the combined structure of the LQG surface and the$$\hbox {CLE}_{\kappa '}$$CLEκin terms of stable growth-fragmentation trees or their variants, which also appear in the asymptotic study of peeling processes on decorated planar maps. This has consequences for questions that do a priori not involve LQG surfaces: In our paper entitled “CLE Percolations” described the law of interfaces obtained when coloring the loops of a$$\hbox {CLE}_{\kappa '}$$CLEκindependently into two colors with respective probabilitiespand$$1-p$$1-p. This description was complete up to one missing parameter$$\rho $$ρ. The results of the present paper about CLE on LQG allow us to determine its value in terms ofpand$$\kappa '$$κ. It shows in particular that$$\hbox {CLE}_{\kappa '}$$CLEκand$$\hbox {CLE}_{16/\kappa '}$$CLE16/κare related via a continuum analog of the Edwards-Sokal coupling between$$\hbox {FK}_q$$FKqpercolation and theq-state Potts model (which makes sense even for non-integerqbetween 1 and 4) if and only if$$q=4\cos ^2(4\pi / \kappa ')$$q=4cos2(4π/κ). This provides further evidence for the long-standing belief that$$\hbox {CLE}_{\kappa '}$$CLEκand$$\hbox {CLE}_{16/\kappa '}$$CLE16/κrepresent the scaling limits of$$\hbox {FK}_q$$FKqpercolation and theq-Potts model whenqand$$\kappa '$$κare related in this way. Another consequence of the formula for$$\rho (p,\kappa ')$$ρ(p,κ)is the value of half-plane arm exponents for such divide-and-color models (a.k.a. fuzzy Potts models) that turn out to take a somewhat different form than the usual critical exponents for two-dimensional models.

     
    more » « less
  4. Abstract

    The Dushnik–Miller dimension of a posetPis the leastdfor whichPcan be embedded into a product ofdchains. Lewis and Souza isibility order on the interval of integers$$[N/\kappa , N]$$[N/κ,N]is bounded above by$$\kappa (\log \kappa )^{1+o(1)}$$κ(logκ)1+o(1)and below by$$\Omega ((\log \kappa /\log \log \kappa )^2)$$Ω((logκ/loglogκ)2). We improve the upper bound to$$O((\log \kappa )^3/(\log \log \kappa )^2).$$O((logκ)3/(loglogκ)2).We deduce this bound from a more general result on posets of multisets ordered by inclusion. We also consider other divisibility orders and give a bound for polynomials ordered by divisibility.

     
    more » « less
  5. Abstract

    The Eden cell growth model is a simple discrete stochastic process which produces a “blob” (aggregation of cells) in $$\mathbb {R}^d$$Rd: start with one cube in the regular grid, and at each time step add a neighboring cube uniformly at random. This process has been used as a model for the growth of aggregations, tumors, and bacterial colonies and the healing of wounds, among other natural processes. Here, we study the topology and local geometry of the resulting structure, establishing asymptotic bounds for Betti numbers. Our main result is that the Betti numbers at timetgrow at a rate between$$t^{(d-1)/d}$$t(d-1)/dand$$P_d(t)$$Pd(t), where$$P_d(t)$$Pd(t)is the size of the site perimeter. Assuming a widely believed conjecture, this establishes the rate of growth of the Betti numbers in every dimension. We also present the results of computational experiments on finer aspects of the geometry and topology, such as persistent homology and the distribution of shapes of holes.

     
    more » « less