Fast convergence of the Glauber dynamics for sampling independent sets

DOI<229::AID-RSA3>3.0.CO;2-X 10.1002/(SICI)1098-2418(199910/12)15:3/4<229::AID-RSA3>3.0.CO;2-XzbMath0941.65010OpenAlexW2073608764MaRDI QIDQ4704791

Michael Luby, Eric Vigoda

Publication date: 7 August 2000

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199910/12)15:3/4<229::aid-rsa3>3.0.co;2-x

zbMATH Keywords

convergenceMarkov chain Monte Carlo methodGlauber dynamicstriangle-free graphssampling independent sets

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Numerical analysis or methods applied to Markov chains (65C40) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Markov chain decomposition for convergence rate analysis, Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs, A probabilistic approach to convex \((\phi)\)-entropy decay for Markov chains, Algorithms to approximately count and sample conforming colorings of graphs, A Graph Polynomial for Independent Sets of Bipartite Graphs, The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs, Nonmonotonicity of phase transitions in a loss network with controls, Slow mixing of Markov chains using fault lines and fat contours, How to couple from the past using a read-once source of randomness, The complexity of approximating bounded-degree Boolean \(\#\)CSP, Approximation via Correlation Decay When Strong Spatial Mixing Fails, Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model, Analyzing Glauber dynamics by comparison of Markov chains, Approximating permanents and hafnians, Cutoff for General Spin Systems with Arbitrary Boundary Conditions, Perfect Simulation for Image Restoration, Glauber dynamics on trees: Boundary conditions and mixing time, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, On systematic scan for sampling H-colorings of the path, Sampling independent sets in the discrete torus, Tunneling of the hard‐core model on finite triangular lattices, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, Dynamic Sampling from Graphical Models

Cites Work

• Unnamed Item
• Unnamed Item
• Random generation of combinatorial structures from a uniform distribution
• Loss networks
• Percolation and the hard-core lattice gas model
• 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
• The Dobrushin-Shlosman phase uniqueness criterion and applications to hard squares
• The problem of uniqueness of a Gibbsian random field and the problem of phase transitions
• Exact sampling with coupled Markov chains and applications to statistical mechanics