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

DOI10.1007/s00440-012-0421-8zbMath1341.82019arXiv1105.0914MaRDI QIDQ1955841

Prasad Tetali, Eric Vigoda, Linji Yang, Jinwoo Shin, 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 algorithm; phase transition; Glauber dynamics; lattice gas; Gibbs measures

Mathematics Subject Classification ID

60K40: Other physical applications of random processes

82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms

Related Items

Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Approximating the partition function of planar two-state spin systems, Spatial mixing and the connective constant: optimal bounds, Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs, Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions

Cites Work

• Unnamed Item
• 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
• 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