The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma

Abstract

We elucidate the close connection between the repulsive lattice gas in equilibrium statistical mechanics and the Lovasz local lemma in probabilistic combinatorics. We show that the conclusion of the Lovasz local lemma holds for dependency graph G and probabilities {p_x} if and only if the independent-set polynomial for G is nonvanishing in the polydisc of radii {p_x}. Furthermore, we show that the usual proof of the Lovasz local lemma -- which provides a sufficient condition for this to occur -- corresponds to a simple inductive argument for the nonvanishing of the independent-set polynomial in a polydisc, which was discovered implicitly by Shearer and explicitly by Dobrushin. We also present some refinements and extensions of both arguments, including a generalization of the Lovasz local lemma that allows for "soft" dependencies. In addition, we prove some general properties of the partition function of a repulsive lattice gas, most of which are consequences of the alternating-sign property for the Mayer coefficients. We conclude with a brief discussion of the repulsive lattice gas on countably infinite graphs.

LaTex2e, 97 pages. Version 2 makes slight changes to improve clarity. To be published in J. Stat. Phys

References in corpus (1)

• A Family of Well-Covered Graphs with Unimodal Independence Polynomials

Cited by in corpus (75)

• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Cluster expansion for abstract polymer models. New bounds from an old approach
• The Lee-Yang and Pólya-Schur Programs. I. Linear Operators Preserving Stability
• The Lee-Yang and Pólya-Schur Programs. II. Theory of Stable Polynomials and Applications
• Multiple Phase Transitions in Extended Hard Core Lattice Gas Models in Two Dimensions
• Structured matrices, continued fractions, and root localization of polynomials
• Algorithmic Pirogov-Sinai theory
• Complex zero-free regions at large |q| for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• Cluster expansion in the canonical ensemble
• On the convergence of cluster expansions for polymer gases
• Fisher zeros and correlation decay in the Ising model
• Cluster expansions for Gibbs point processes
• When a local Hamiltonian must be frustration-free
• Independent sets in the hypercube revisited
• Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids
• Inapproximability of the independent set polynomial in the complex plane
• An Improvement of the Lovász Local Lemma via Cluster Expansion
• Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
• Central limit theorems and the geometry of polynomials
• A ridiculously simple and explicit implicit function theorem
• On the phase transitions of graph coloring and independent sets
• On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
• Correlation decay and partition function zeros: Algorithms and phase transitions
• Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
• Disagreement percolation for the hard-sphere model
• Covering systems with restricted divisibility
• The correlation decay (CD) tree and strong spatial mixing in multi-spin systems
• Exponential Time Complexity of Weighted Counting of Independent Sets
• On a conjecture of Sokal concerning roots of the independence polynomial
• Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs
• Algorithmic Cluster Expansions for Quantum Problems
• Some variants of the exponential formula, with application to the multivariate Tutte polynomial (alias Potts model)
• Computing the partition function for cliques in a graph
• A local lemma via entropy compression
• Uniform Sampling through the Lovász Local Lemma
• Approximating permanents and hafnians
• K-independent percolation on trees
• Benjamini--Schramm continuity of root moments of graph polynomials
• Sufficient conditions for uniform bounds in abstract polymer systems and explorative partition schemes
• Shearer's measure and stochastic domination of product measures
• Improved bounds on coloring of graphs
• Cluster expansions: Necessary and sufficient convergence conditions
• Uniqueness thresholds on trees versus graphs
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Absence of zeros implies strong spatial mixing
• Zero-free regions of partition functions with applications to algorithms and graph limits
• Novel Bounds on Marginal Probabilities
• The limit of the zero locus of the independence polynomial for bounded degree graphs
• Variable Version Lovász Local Lemma: Beyond Shearer's Bound
• On trees with real rooted independence polynomial
• Shearer's point process and the hard-sphere model in one dimension
• Fundamentals of Partial Rejection Sampling
• A generalization of Schönemann's theorem via a graph theoretic method
• Hypergraph independence polynomials with a zero close to the origin
• Convergence of cluster and virial expansions for repulsive classical gases
• Power series expansions for the planar monomer-dimer problem
• An asymptotic formula for the zeros of the deformed exponential function
• On the location of roots of the independence polynomial of bounded degree graphs
• Computing the permanent of (some) complex matrices
• Extensions of the Algorithmic Lovasz Local Lemma
• Zeros of the deformed exponential function
• Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
• Quantum Lovász Local Lemma: Shearer's Bound is Tight
• Transversals in generalized Latin squares
• Recursion relations for chromatic coefficients for graphs and hypergraphs
• A constructive algorithm for the LLL on permutations
• Witness trees in the Moser-Tardos algorithmic Lovász Local Lemma and Penrose trees in the hard core lattice gas
• The arithmetic Tutte polynomials of the classical root systems
• The Blume-Emery-Griffiths model at the FAD and AD interfaces
• Shearer's point process, the hard-sphere model and a continuum Lovász Local Lemma
• $PC$-polynomial of graph
• Structure theorems for Power Series in Several Complex Variables
• Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections
• Computing the probability of intersection