The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
From MaRDI portal
(Redirected from Publication:2487791)
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.
Recommendations
Cites work
- A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
- A parallel algorithmic version of the local lemma
- A remark on high temperature polymer expansion for lattice systems with infinite range pair interactions
- A simple inductive approach to the problem of convergence of cluster expansions of polymer models
- Almost sure entropy and the variational principle for random fields with unbounded state space
- Amenability and phase transition in the Ising model
- An algorithmic approach to the Lovász local lemma. I
- Asymptotic lower bounds for Ramsey functions
- Chromatic Roots are Dense in the Whole Complex Plane
- Clique polynomials and independent set polynomials of graphs
- Cluster expansion for abstract polymer models
- Compactness and the maximal Gibbs state for random Gibbs fields on a lattice
- Convergence of Fugacity Expansions for Fluids and Lattice Gases
- Coulomb systems at low density: a review.
- Dependence polynomials
- Entropy, independent sets and antichains: A new approach to Dedekind's problem
- Ergodicity of the hard-core model on \(\mathbb{Z}^ 2\) with parity-dependent activities
- High-dimensional lattice gases
- Homogeneous multivariate polynomials with the half-plane property
- scientific article; zbMATH DE number 2077692 (Why is no real title available?)
- scientific article; zbMATH DE number 3190209 (Why is no real title available?)
- Irreducibility of the Tutte polynomial of a connected matroid
- Lopsided Lovász Local lemma and Latin transversals
- Mayer expansions and the Hamilton-Jacobi equation. II: Fermions, dimensional reduction formulas.
- New versions of Suen's correlation inequality
- Nonmonotonic behavior in hard-core and Widom-Rowlinson models
- On a problem of Spencer
- On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
- On the generalized pantograph functional-differential equation
- On the numbers of independent k-sets in a claw free graph
- Percolation and the hard-core lattice gas model
- Polymer gas approach to \(N\)-body lattice systems
- Potts model on infinite graphs and the limit of chromatic polynomials
- Ramsey's theorem - a new lower bound
- Regularity properties and pathologies of position-space renormalization-group transformations: scope and limitations of Gibbsian theory
- Rogers-Ramanujan identities in the hard hexagon model
- Roots of independence polynomials of well covered graphs
- The numbers of dependent \(k\)-sets in a graph are log concave
- The problem of uniqueness of a Gibbsian random field and the problem of phase transitions
- The rational maps z\mapsto 1+1/\omega z^d have no Herman rings
- Theory of monomer-dimer systems
- TRANSFER-MATRIX STUDY OF NEGATIVE-FUGACITY SINGULARITY OF HARD-CORE LATTICE GAS
- Two theorems on classical many-particle systems
Cited in
(99)- Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
- Zeros of the deformed exponential function
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- The Ising partition function: zeros and deterministic approximation
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- On the stability of independence polynomials
- On trees with real-rooted independence polynomial
- Enumeration of substitutional isomers with restrictive mutual positions of ligands: I. Overall counts
- A proof of the upper matching conjecture for large graphs
- Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion
- Entropy compression versus Lovász local lemma
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Recursion relations for chromatic coefficients for graphs and hypergraphs
- Cluster expansions: necessary and sufficient convergence conditions
- Implementations and the independent set polynomial below the Shearer threshold
- The method of cumulants for the normal approximation
- Algorithmic Pirogov-Sinai theory
- Convergence of cluster and virial expansions for repulsive classical gases
- Proof of the Kalai-Meshulam conjecture
- Cayley trees do not determine the maximal zero-free locus of the independence polynomial
- Sufficient conditions for uniform bounds in abstract polymer systems and explorative partition schemes
- Disagreement percolation for the hard-sphere model
- Covering systems with restricted divisibility
- On a conjecture of Sokal concerning roots of the independence polynomial
- A generalization of Schönemann's theorem via a graph theoretic method
- Generalizations of the matching polynomial to the multivariate independence polynomial
- Counting regions with bounded surface area
- Cluster expansion for abstract polymer models. New bounds from an old approach
- Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- Analyticity for classical gasses via recursion
- An asymptotic formula for the zeros of the deformed exponential function
- Computing the permanent of (some) complex matrices
- The density Turán problem
- Finitely dependent coloring
- Exponential Time Complexity of Weighted Counting of Independent Sets
- An improvement of the Lovász local lemma via cluster expansion
- Algorithms for \#BIS-hard problems on expander graphs
- Long paths and connectivity in 1-independent random graphs
- Bounds For The Real Zeros of Chromatic Polynomials
- Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs
- Improved bounds on coloring of graphs
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Shearer's measure and stochastic domination of product measures
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Approximating permanents and hafnians
- Note on the smallest root of the independence polynomial
- An algorithmic proof of the Lovász local lemma via resampling oracles
- Quasirandom graphs and the pantograph equation
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- The bipermutahedron
- Fisher Zeros and Correlation Decay in the Ising Model
- On the number of r-matchings in a tree
- Inapproximability of the independent set polynomial in the complex plane
- Independent sets in the hypercube revisited
- Cluster expansions for Gibbs point processes
- Fisher zeros and correlation decay in the Ising model
- Approximating real-rooted and stable polynomials, with combinatorial applications
- Transversals in generalized Latin squares
- Shearer's point process, the hard-sphere model, and a continuum Lovász local lemma
- Partially independent random variables
- On independent sets in graphs with given minimum degree
- Gauges, loops, and polynomials for partition functions of graphical models
- Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
- Absence of zeros implies strong spatial mixing
- Correlation decay and the absence of zeros property of partition functions
- The Blume-Emery-Griffiths model on the FAD point and on the AD line
- Homomorphisms from the torus
- One-dependent colorings of the star graph
- Independence polynomials and hypergeometric series
- Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
- Asymptotic behavior of a generalized independent sets model on the two-dimensional Sierpinski gasket
- Fundamentals of partial rejection sampling
- On the zeroes of hypergraph independence polynomials
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- Central limit theorems and the geometry of polynomials
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Variable version Lovász local lemma: a tale of two boundaries
- Hypergraph independence polynomials with a zero close to the origin
- On the zero-free region for the chromatic polynomial of graphs with maximum degree and girth g
- On Vizing's problem for triangle-free graphs
- On the evolution of structure in triangle-free graphs
- Correlation decay and partition function zeros: algorithms and phase transitions
- A remark on the Whitney broken circuit theorem
- Cluster expansion in the canonical ensemble
- The limit of the zero locus of the independence polynomial for bounded degree graphs
- Fast sampling via spectral independence beyond bounded-degree graphs
- Local approximations of the independent set polynomial
- On Dedekind's problem, a sparse version of Sperner's theorem, and antichains of a given size in the Boolean lattice
- On series expansions of zeros of the deformed exponential function
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- \(k\)-independent percolation on trees
- The Lee--Yang and Pólya--Schur programs. I: Linear operators preserving stability
- Computing the partition function for graph homomorphisms with multiplicities
- Benjamini-Schramm continuity of root moments of graph polynomials
- Uniqueness thresholds on trees versus graphs
- The bivariate Ising polynomial of a graph
- The independence polynomial of rooted products of graphs
- On the convergence of cluster expansions for polymer gases
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)
