Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs

DOI10.1137/18M1219722zbMath1436.82004OpenAlexW3013409926MaRDI QIDQ5220472

Eric Vigoda, Antonio Blanca, Daniel Štefanković, Kuan Yang, Andreas Galanis, Leslie Ann Goldberg

Publication date: 26 March 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1219722

zbMATH Keywords

samplingphase transitionsrandom regular graphsPotts model

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Phase transitions (general) in equilibrium statistical mechanics (82B26) Percolation (82B43) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Randomized algorithms (68W20) Statistical mechanics of magnetic materials (82D40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (9)

Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree ⋮ Counting Solutions to Random CNF Formulas ⋮ The Swendsen–Wang dynamics on trees ⋮ Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \) ⋮ Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs ⋮ Metastability of the Potts ferromagnet on random regular graphs ⋮ Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs ⋮ Random-cluster dynamics on random regular graphs in tree uniqueness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The self-dual point of the two-dimensional random-cluster model is critical for \(q \geqslant 1\)
• On the hardness of sampling independent sets beyond the tree threshold
• Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
• Approach to equilibrium of Glauber dynamics in the one phase region. II: The general case
• For 2-D lattice spin systems weak mixing implies strong mixing
• The random cluster model on a general graph and a phase transition characterization of nonamenability
• Uniqueness of uniform random colorings of regular trees
• Glauber dynamics on trees and hyperbolic graphs
• Bound on the mass gap for finite volume stochastic Ising models at low temperature
• Mixing properties and exponential decay for lattice systems in finite volumes.
• The random-cluster model on a homogeneous tree
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Approximating partition functions of the two-state spin system
• Uniqueness for the 3-state antiferromagnetic Potts model on the tree
• Spatial mixing and the connective constant: optimal bounds
• The replica symmetric solution for Potts models on \(d\)-regular graphs
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Counting independent sets up to the tree threshold
• Introduction to Random Graphs
• Rapid mixing of Gibbs sampling on graphs that are sparse on average
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• Information, Physics, and Computation
• Sampling Random Colorings of Sparse Random Graphs
• Sampling in Potts Model on Sparse Random Graphs
• Algorithmic Pirogov-Sinai theory
• Algorithms for #BIS-hard problems on expander graphs
• The Random-Cluster Model
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold

This page was built for publication: Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs