Low-temperature sampling on sparse random graphs

DOI10.1214/26-EJP1576MaRDI QIDQ7324039zbMATH OpenFDO

Authors Andreas Galanis, Leslie Ann Goldberg, Paulina Smolarova

Publication date 2 September 2026

Published in Electronic Journal of Probability (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://projecteuclid.org/journals/electronic-journal-of-probability/volume-31/issue-none/Low-temperature-sampling-on-sparse-random-graphs/10.1214/26-EJP1576.full

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Probabilistic models, generic numerical methods in probability and statistics (65C20)

Cites work

• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• A spectral approach to approximately counting independent sets in dense bipartite graphs
• Algorithmic Pirogov-Sinai theory
• Algorithms for \#BIS-hard problems on expander graphs
• Algorithms for the ferromagnetic Potts model on expanders
• An efficient algorithm for the complex roots problem
• Anatomy of the giant component: the strictly supercritical regime
• Approximately counting independent sets in bipartite graphs via graph containers
• Approximating the partition function of the ferromagnetic Potts model
• Cluster expansion for abstract polymer models
• Concentration of multi-overlaps for random dilute ferromagnetic spin models
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• Fast algorithms at low temperatures via Markov chains†
• Fast algorithms for general spin systems on bipartite expanders
• Fast mixing in sparse random Ising models
• Fast mixing via polymers for random graphs with unbounded degree
• Fast sampling via spectral independence beyond bounded-degree graphs
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1559583 (Why is no real title available?)
• scientific article; zbMATH DE number 7561741 (Why is no real title available?)
• Low-temperature Ising dynamics with random initializations
• On the mixing time of Glauber dynamics for the hard-core and related models on G(n,d/n)
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Rapid mixing of global Markov chains via spectral independence: the unbounded degree case
• Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics
• Sampling in Potts model on sparse random graphs
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Sampling random colorings of sparse random graphs
• Sampling, counting, and large deviations for triangle-free graphs near the critical density
• Spatial mixing and the random-cluster dynamics on lattices
• Symbolic integration
• The Swendsen–Wang dynamics on trees

This page was built for publication: Low-temperature sampling on sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7324039)