More Like this

1. Random-Cluster Dynamics on Random Regular Graphs in Tree Uniqueness

   https://doi.org/10.1007/s00220-021-04093-z  

   Blanca, Antonio ; Gheissari, Reza ( April 2021 , Communications in Mathematical Physics)

   We establish rapid mixing of the random-cluster Glauber dynamics on random$$\varDelta $$$\Delta$-regular graphs for all$$q\ge 1$$$q\ge 1$and$$p$p<p_u(q,\Delta )$, where the threshold$$p_u(q,\varDelta )$$$p_u(q,\Delta )$corresponds to a uniqueness/non-uniqueness phase transition for the random-cluster model on the (infinite)$$\varDelta $$$\Delta$-regular tree. It is expected that this threshold is sharp, and for$$q>2$$$q>2$the Glauber dynamics on random$$\varDelta $$$\Delta$-regular graphs undergoes an exponential slowdown at$$p_u(q,\varDelta )$$$p_u(q,\Delta )$. More precisely, we show that for every$$q\ge 1$$$q\ge 1$,$$\varDelta \ge 3$$$\Delta \ge 3$, and$$p$p<p_u(q,\Delta )$, with probability$$1-o(1)$$$1-o\left(1\right)$over the choice of a random$$\varDelta $$$\Delta$-regular graph onnvertices, the Glauber dynamics for the random-cluster model has$$\varTheta (n \log n)$$$\Theta (nlogn)$mixing time. As a corollary, we deduce fast mixing of the Swendsen–Wang dynamics for the Potts model on random$$\varDelta $$$\Delta$-regular graphs for every$$q\ge 2$$$q\ge 2$, 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. Metastability of the Potts Ferromagnet on Random Regular Graphs

   Coja-Oghlan, Amin ; Galanis, Andreas ; Goldberg, Leslie Ann ; Ravelomanana, Jean Bernoulli ; Štefankovič, Daniel ; Vigoda, Eric ( June 2022 , ICALP 2022)

   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. Non-simple conformal loop ensembles on Liouville quantum gravity and the law of CLE percolation interfaces

   https://doi.org/10.1007/s00440-021-01070-4  

   Miller, Jason ; Sheffield, Scott ; Werner, Wendelin ( June 2021 , Probability Theory and Related Fields)

   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 '}$$${\text{CLE}}_{{\kappa }^{\prime }}$for$$\kappa '$$${\kappa }^{\prime }$in (4, 8) that is drawn on an independent$$\gamma $$$\gamma$-LQG surface for$$\gamma ^2=16/\kappa '$$${\gamma }^2=16/{\kappa }^{\prime }$. The results are similar in flavor to the ones from our companion paper dealing with$$\hbox {CLE}_{\kappa }$$${\text{CLE}}_{\kappa }$for$$\kappa $$$\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 '}$$${\text{CLE}}_{{\kappa }^{\prime }}$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 '}$$${\text{CLE}}_{{\kappa }^{\prime }}$independently into two colors with respective probabilitiespand$$1-p$$$1-p$. This description was complete up to one missing parameter$$\rho $$$\rho$. The results of the present paper about CLE on LQG allow us to determine its value in terms ofpand$$\kappa '$$${\kappa }^{\prime }$. It shows in particular that$$\hbox {CLE}_{\kappa '}$$${\text{CLE}}_{{\kappa }^{\prime }}$and$$\hbox {CLE}_{16/\kappa '}$$${\text{CLE}}_{16/{\kappa }^{\prime }}$are related via a continuum analog of the Edwards-Sokal coupling between$$\hbox {FK}_q$$${\text{FK}}_q$percolation 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=4{cos}^2(4\pi /{\kappa }^{\prime })$. This provides further evidence for the long-standing belief that$$\hbox {CLE}_{\kappa '}$$${\text{CLE}}_{{\kappa }^{\prime }}$and$$\hbox {CLE}_{16/\kappa '}$$${\text{CLE}}_{16/{\kappa }^{\prime }}$represent the scaling limits of$$\hbox {FK}_q$$${\text{FK}}_q$percolation and theq-Potts model whenqand$$\kappa '$$${\kappa }^{\prime }$are related in this way. Another consequence of the formula for$$\rho (p,\kappa ')$$$\rho (p,{\kappa }^{\prime })$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. The Dimension of Divisibility Orders and Multiset Posets

   https://doi.org/10.1007/s11083-023-09653-7  

   Haiman, Milan ( November 2023 , Order)

   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/\kappa ,N]$is bounded above by$$\kappa (\log \kappa )^{1+o(1)}$$$\kappa {(log\kappa )}^{1+o\left(1\right)}$and below by$$\Omega ((\log \kappa /\log \log \kappa )^2)$$$\Omega \left({(log\kappa /loglog\kappa )}^2\right)$. We improve the upper bound to$$O((\log \kappa )^3/(\log \log \kappa )^2).$$$O({(log\kappa )}^3/{(loglog\kappa )}^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. Topology and Local Geometry of the Eden Model

   https://doi.org/10.1007/s00454-022-00474-w  

   Manin, Fedor ; Roldán, Érika ; Schweinhart, Benjamin ( February 2023 , Discrete & Computational Geometry)

   The Eden cell growth model is a simple discrete stochastic process which produces a “blob” (aggregation of cells) in $$\mathbb {R}^d$$$R^d$: 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)/d}$and$$P_d(t)$$$P_d\left(t\right)$, where$$P_d(t)$$$P_d\left(t\right)$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