Improved mixing condition on the grid for counting and sampling independent sets

DOI10.1109/FOCS.2011.45zbMath1341.82019arXiv1105.0914OpenAlexW2568660165MaRDI QIDQ1955841

Jinwoo Shin, Linji Yang, Prasad Tetali, Eric Vigoda, Ricardo L. Restrepo

Publication date: 19 June 2013

Published in: Probability Theory and Related Fields, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1105.0914

zbMATH Keywords

approximation algorithmphase transitionGlauber dynamicslattice gasGibbs measures

Mathematics Subject Classification ID

Other physical applications of random processes (60K40) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (16)

Spatial mixing and the connective constant: optimal bounds ⋮ The Blume-Emery-Griffiths model on the FAD point and on the AD line ⋮ A stochastic approach to shortcut bridging in programmable matter ⋮ Approximation Algorithms for the Random Field Ising Model ⋮ Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models ⋮ Analyticity for classical gasses via recursion ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Counting hypergraph matchings up to uniqueness threshold ⋮ Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs ⋮ Approximating the partition function of planar two-state spin systems ⋮ Phase Coexistence for the Hard-Core Model on ℤ² ⋮ Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems ⋮ Deterministic counting of graph colourings using sequences of subgraphs ⋮ Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• The self-dual point of the two-dimensional random-cluster model is critical for \(q \geqslant 1\)
• Random generation of combinatorial structures from a uniform distribution
• Loss networks
• Gibbs measures and phase transitions
• 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 complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Nonmonotonic behavior in hard-core and Widom-Rowlinson models
• The Ising model and percolation on trees and tree-like graphs
• The Dobrushin-Shlosman phase uniqueness criterion and applications to hard squares
• Improved upper bounds for self-avoiding walks in \(\mathbb Z^d\)
• The problem of uniqueness of a Gibbsian random field and the problem of phase transitions
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Slow mixing of glauber dynamics via topological obstructions
• The Complexity of Enumeration and Reliability Problems
• Upper Bounds for the Connective Constant of Self-Avoiding Walks
• Mixing in time and space for lattice spin systems: A combinatorial view
• A new lower bound for the critical probability of site percolation on the square lattice
• Cylindrical Algebraic Decomposition I: The Basic Algorithm
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
• Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields

This page was built for publication: Improved mixing condition on the grid for counting and sampling independent sets