Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs

DOI10.1214/22-aihp1263arXiv2006.11580OpenAlexW3036557947MaRDI QIDQ6157383

Will Perkins, Tyler Helmuth, Matthew Jenssen

Publication date: 21 June 2023

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.11580

zbMATH Keywords

Markov chainsphase transitionsrandom graphsPotts modelrandom cluster modelapproximate counting

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Phase transitions (general) in equilibrium statistical mechanics (82B26) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Critical phenomena in equilibrium statistical mechanics (82B27)

Related Items

Homomorphisms from the torus, Metastability of the Potts ferromagnet on random regular graphs, Approximation Algorithms for the Random Field Ising Model

Cites Work

• Unnamed Item
• Unnamed Item
• Counting in two-spin models on \(d\)-regular graphs
• The weak limit of Ising models on locally tree-like graphs
• Quenched central limit theorems for the Ising model on random graphs
• Interfaces in the Potts model. I: Pirogov-Sinai theory of the Fortuin- Kasteleyn representation
• Ising models on locally tree-like graphs
• Cutoff phenomena for random walks on random regular graphs
• Cluster expansion for abstract polymer models
• The isoperimetric number of random regular graphs
• The asymptotic distribution of short cycles in random regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Random cluster dynamics for the Ising model is rapidly mixing
• Charting the replica symmetric phase
• Short cycles in random regular graphs
• The relative complexity of approximate counting problems
• The random-cluster model on a homogeneous tree
• The Swendsen-Wang process does not always mix rapidly
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Algorithmic Pirogov-Sinai theory
• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• The replica symmetric solution for Potts models on \(d\)-regular graphs
• Fast mixing via polymers for random graphs with unbounded degree
• Improved inapproximability results for counting independent sets in the hard-core model
• Loop series for discrete statistical models on graphs
• Counting independent sets up to the tree threshold
• Polynomial-Time Approximation Algorithms for the Ising Model
• Approximating the Permanent
• Lectures on the Ising and Potts Models on the Hypercubic Lattice
• Anomalous finite size corrections in random field models
• Algorithms for #BIS-Hard Problems on Expander Graphs
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• Expander graphs and their applications
• Approximating the Partition Function of the Ferromagnetic Potts Model
• Mathematical Aspects of Mixing Times in Markov Chains
• Information, Physics, and Computation
• The Freezing Threshold for k -Colourings of a Random Graph
• Swendsen‐Wang algorithm on the mean‐field Potts model
• Mixing Times of Critical Two‐Dimensional Potts Models
• Left and right convergence of graphs with bounded degree
• The replica symmetric phase of random constraint satisfaction problems
• Independent sets in the hypercube revisited
• Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures
• Counting independent sets in unbalanced bipartite graphs
• On the Number of Solutions in Random Graphk-Colouring
• Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
• Weighted counting of solutions to sparse systems of equations
• Dynamics for the mean-field random-cluster model
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Gibbs states and the set of solutions of random constraint satisfaction problems
• The Random-Cluster Model
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs