Rapid mixing of Gibbs sampling on graphs that are sparse on average
From MaRDI portal
Publication:3055775
DOI10.1002/rsa.20276zbMath1216.60054arXiv0704.3603OpenAlexW3083665005MaRDI QIDQ3055775
Publication date: 9 November 2010
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0704.3603
Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)
Related Items
Spatial mixing and the connective constant: optimal bounds, Exact thresholds for Ising-Gibbs samplers on general graphs, Approximating partition functions of the two-state spin system, Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics, Unnamed Item, Metastability of the Ising model on random regular graphs at zero temperature, Uniqueness for the 3-state antiferromagnetic Potts model on the tree, Gibbs rapidly samples colorings of \(G(n, d/n)\), Random-cluster dynamics on random regular graphs in tree uniqueness, Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs, Deterministic counting of graph colourings using sequences of subgraphs, Unnamed Item
Cites Work
- Unnamed Item
- The logarithmic Sobolev inequality for discrete spin systems on a lattice
- Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
- A note on the Glauber dynamics for sampling independent sets
- Glauber dynamics on trees: Boundary conditions and mixing time
- Robust phase transitions for Heisenberg and other models on general trees
- The Ising model and percolation on trees and tree-like graphs
- On log-Sobolev inequalities for infinite lattice systems
- Randomly coloring constant degree graphs
- Counting independent sets up to the tree threshold
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Polynomial-Time Approximation Algorithms for the Ising Model
- On Counting Independent Sets in Sparse Graphs
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- Mixing in time and space for lattice spin systems: A combinatorial view
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- On Markov Chains for Independent Sets
- Strong Spatial Mixing with Fewer Colors for Lattice Graphs
