A note on the Glauber dynamics for sampling independent sets

zbMath0967.68172MaRDI QIDQ1594581

Eric Vigoda

Publication date: 8 February 2001

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/121186

zbMATH Keywords

samplingGlauber dynamics

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20)

Related Items (16)

Spatial mixing and the connective constant: optimal bounds ⋮ A probabilistic approach to convex \((\phi)\)-entropy decay for Markov chains ⋮ Sampling Edge Covers in 3-Regular Graphs ⋮ Coupling with the stationary distribution and improved sampling for colorings and independent sets ⋮ Correlation decay for hard spheres via Markov chains ⋮ Logarithmic Sobolev inequalities for finite spin systems and applications ⋮ A general lower bound for mixing of single-site dynamics on graphs ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Cutoff for General Spin Systems with Arbitrary Boundary Conditions ⋮ Glauber dynamics on trees: Boundary conditions and mixing time ⋮ Mixing of Markov chains for independent sets on chordal graphs with bounded separators ⋮ Rapid mixing of Gibbs sampling on graphs that are sparse on average ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ Gibbs rapidly samples colorings of \(G(n, d/n)\) ⋮ On the hardness of sampling independent sets beyond the tree threshold ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model

This page was built for publication: A note on the Glauber dynamics for sampling independent sets