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

DOI10.1007/S10955-004-2055-4zbMATH Open1107.82013arXivcond-mat/0309352OpenAlexW2157869188WikidataQ56893206 ScholiaQ56893206MaRDI QIDQ2487791FDOQ2487791

Authors: Alan D. Sokal, Alex Scott 

Publication date: 8 August 2005

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cond-mat/0309352

Recommendations

• On Dependency Graphs and the Lattice Gas
• An improvement of the Lovász local lemma via cluster expansion
• Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
• Directed Lovász local lemma and Shearer's lemma
• Moser and tardos meet Lovász

zbMATH Keywords

independent-set polynomialLovasz local lemmaMayer expansionsrepulsive lattice gas

Mathematics Subject Classification ID

Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Graph theory (05C99)

Cites Work

• Theory of monomer-dimer systems
• Percolation and the hard-core lattice gas model
• Homogeneous multivariate polynomials with the half-plane property
• Roots of independence polynomials of well covered graphs
• Dependence polynomials
• On the generalized pantograph functional-differential equation
• Title not available (Why is that?)
• Cluster expansion for abstract polymer models
• A simple inductive approach to the problem of convergence of cluster expansions of polymer models
• A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
• A remark on high temperature polymer expansion for lattice systems with infinite range pair interactions
• Amenability and phase transition in the Ising model
• Clique polynomials and independent set polynomials of graphs
• On the numbers of independent \(k\)-sets in a claw free graph
• Coulomb systems at low density: a review.
• The problem of uniqueness of a Gibbsian random field and the problem of phase transitions
• New versions of Suen's correlation inequality
• Two theorems on classical many-particle systems
• Convergence of Fugacity Expansions for Fluids and Lattice Gases
• An algorithmic approach to the Lovász local lemma. I
• Ramsey's theorem - a new lower bound
• Asymptotic lower bounds for Ramsey functions
• Regularity properties and pathologies of position-space renormalization-group transformations: scope and limitations of Gibbsian theory
• Chromatic Roots are Dense in the Whole Complex Plane
• Potts model on infinite graphs and the limit of chromatic polynomials
• Polymer gas approach to \(N\)-body lattice systems
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
• Lopsided Lovász Local lemma and Latin transversals
• Entropy, independent sets and antichains: A new approach to Dedekind's problem
• On a problem of Spencer
• Nonmonotonic behavior in hard-core and Widom-Rowlinson models
• A parallel algorithmic version of the local lemma
• Compactness and the maximal Gibbs state for random Gibbs fields on a lattice
• Irreducibility of the Tutte polynomial of a connected matroid
• High-dimensional lattice gases
• The rational maps $z\mapsto 1+1/\omega z^d$ have no Herman rings
• Rogers-Ramanujan identities in the hard hexagon model
• Title not available (Why is that?)
• Ergodicity of the hard-core model on \(\mathbb{Z}^ 2\) with parity-dependent activities
• Almost sure entropy and the variational principle for random fields with unbounded state space
• Mayer expansions and the Hamilton-Jacobi equation. II: Fermions, dimensional reduction formulas.
• The numbers of dependent \(k\)-sets in a graph are log concave
• TRANSFER-MATRIX STUDY OF NEGATIVE-FUGACITY SINGULARITY OF HARD-CORE LATTICE GAS

Cited In (85)

• Implementations and the independent set polynomial below the Shearer threshold
• Computing the partition function for graph homomorphisms with multiplicities
• The bipermutahedron
• Homomorphisms from the torus
• Covering systems with restricted divisibility
• The Ising partition function: zeros and deterministic approximation
• Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs
• An asymptotic formula for the zeros of the deformed exponential function
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• Algorithms for #BIS-Hard Problems on Expander Graphs
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Computing the permanent of (some) complex matrices
• Entropy compression versus Lovász local lemma
• FINITELY DEPENDENT COLORING
• Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
• On the stability of independence polynomials
• On trees with real-rooted independence polynomial
• The method of cumulants for the normal approximation
• On a conjecture of Sokal concerning roots of the independence polynomial
• Improved bounds on coloring of graphs
• The independence polynomial of rooted products of graphs
• Zeros of the deformed exponential function
• The Lee--Yang and Pólya--Schur programs. I: Linear operators preserving stability
• Independent sets in the hypercube revisited
• A proof of the upper matching conjecture for large graphs
• Cluster Expansions for GIBBS Point Processes
• Uniqueness thresholds on trees versus graphs
• Shearer's measure and stochastic domination of product measures
• \(k\)-independent percolation on trees
• Enumeration of substitutional isomers with restrictive mutual positions of ligands: I. Overall counts
• Independence polynomials and hypergeometric series
• Proof of the Kalai-Meshulam conjecture
• Benjamini-Schramm continuity of root moments of graph polynomials
• An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles
• Bounds For The Real Zeros of Chromatic Polynomials
• Cluster expansion for abstract polymer models. New bounds from an old approach
• Transversals in generalized Latin squares
• An improvement of the Lovász local lemma via cluster expansion
• Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
• Partially Independent Random Variables
• Recursion relations for chromatic coefficients for graphs and hypergraphs
• Counting regions with bounded surface area
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• The density Turán problem
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Approximating permanents and hafnians
• Correlation decay and the absence of zeros property of partition functions
• Inapproximability of the Independent Set Polynomial in the Complex Plane
• Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
• A generalization of Schönemann's theorem via a graph theoretic method
• Algorithmic Pirogov-Sinai theory
• Cluster expansion in the canonical ensemble
• Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
• Cluster expansions: necessary and sufficient convergence conditions
• On the number of \(r\)-matchings in a tree
• Fisher zeros and correlation decay in the Ising model
• Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion
• Note on the smallest root of the independence polynomial
• On the convergence of cluster expansions for polymer gases
• Sufficient conditions for uniform bounds in abstract polymer systems and explorative partition schemes
• The bivariate Ising polynomial of a graph
• Convergence of cluster and virial expansions for repulsive classical gases
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• On Independent Sets in Graphs with Given Minimum Degree
• One-dependent colorings of the star graph
• Asymptotic behavior of a generalized independent sets model on the two-dimensional Sierpinski gasket
• Shearer's point process, the hard-sphere model, and a continuum Lovász local lemma
• Absence of zeros implies strong spatial mixing
• Cayley trees do not determine the maximal zero-free locus of the independence polynomial
• Gauges, loops, and polynomials for partition functions of graphical models
• Fundamentals of partial rejection sampling
• Quasirandom Graphs and the Pantograph Equation
• On the zeroes of hypergraph independence polynomials
• Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
• The Blume-Emery-Griffiths model on the FAD point and on the AD line
• Disagreement percolation for the hard-sphere model
• Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
• Long paths and connectivity in 1‐independent random graphs
• Approximating real-rooted and stable polynomials, with combinatorial applications
• Generalizations of the matching polynomial to the multivariate independence polynomial
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• The complexity of ferromagnetic 2-spin systems on bounded degree graphs
• Analyticity for classical gasses via recursion
• Fisher Zeros and Correlation Decay in the Ising Model

This page was built for publication: The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2487791)