The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
From MaRDI portal
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
- scientific article; zbMATH DE number 2077692 (Why is no real title available?)
- scientific article; zbMATH DE number 3190209 (Why is no real title available?)
- 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
- 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 Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
- On a problem of Spencer
- 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
- TRANSFER-MATRIX STUDY OF NEGATIVE-FUGACITY SINGULARITY OF HARD-CORE LATTICE GAS
- 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
- Two theorems on classical many-particle systems
Cited in
(85)- The Lee--Yang and Pólya--Schur programs. I: Linear operators preserving stability
- Recursion relations for chromatic coefficients for graphs and hypergraphs
- The Ising partition function: zeros and deterministic approximation
- The bipermutahedron
- An asymptotic formula for the zeros of the deformed exponential function
- Counting regions with bounded surface area
- \(k\)-independent percolation on trees
- Cluster expansions for Gibbs point processes
- Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
- Correlation decay and the absence of zeros property of partition functions
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- Enumeration of substitutional isomers with restrictive mutual positions of ligands: I. Overall counts
- Fisher zeros and correlation decay in the Ising model
- The independence polynomial of rooted products of graphs
- Computing the permanent of (some) complex matrices
- Independence polynomials and hypergeometric series
- Partially independent random variables
- Exponential Time Complexity of Weighted Counting of Independent Sets
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- A generalization of Schönemann's theorem via a graph theoretic method
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Entropy compression versus Lovász local lemma
- Inapproximability of the independent set polynomial in the complex plane
- Proof of the Kalai-Meshulam conjecture
- The density Turán problem
- On independent sets in graphs with given minimum degree
- Covering systems with restricted divisibility
- Finitely dependent coloring
- Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs
- Independent sets in the hypercube revisited
- Cluster expansions: necessary and sufficient convergence conditions
- Convergence of cluster and virial expansions for repulsive classical gases
- On a conjecture of Sokal concerning roots of the independence polynomial
- Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion
- A proof of the upper matching conjecture for large graphs
- The bivariate Ising polynomial of a graph
- Algorithmic Pirogov-Sinai theory
- Bounds For The Real Zeros of Chromatic Polynomials
- Note on the smallest root of the independence polynomial
- Cluster expansion for abstract polymer models. New bounds from an old approach
- Algorithms for \#BIS-hard problems on expander graphs
- Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
- On the stability of independence polynomials
- Improved bounds on coloring of graphs
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- An improvement of the Lovász local lemma via cluster expansion
- Transversals in generalized Latin squares
- Approximating permanents and hafnians
- Implementations and the independent set polynomial below the Shearer threshold
- Uniqueness thresholds on trees versus graphs
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- On the number of \(r\)-matchings in a tree
- Cluster expansion in the canonical ensemble
- On the convergence of cluster expansions for polymer gases
- Benjamini-Schramm continuity of root moments of graph polynomials
- Zeros of the deformed exponential function
- Homomorphisms from the torus
- On trees with real-rooted independence polynomial
- Computing the partition function for graph homomorphisms with multiplicities
- Sufficient conditions for uniform bounds in abstract polymer systems and explorative partition schemes
- Shearer's measure and stochastic domination of product measures
- An algorithmic proof of the Lovász local lemma via resampling oracles
- Gauges, loops, and polynomials for partition functions of graphical models
- Absence of zeros implies strong spatial mixing
- Fisher Zeros and Correlation Decay in the Ising Model
- Generalizations of the matching polynomial to the multivariate independence polynomial
- Fundamentals of partial rejection sampling
- Approximating real-rooted and stable polynomials, with combinatorial applications
- The method of cumulants for the normal approximation
- The Blume-Emery-Griffiths model on the FAD point and on the AD line
- Shearer's point process, the hard-sphere model, and a continuum Lovász local lemma
- Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
- Cayley trees do not determine the maximal zero-free locus of the independence polynomial
- One-dependent colorings of the star graph
- On the zeroes of hypergraph independence polynomials
- Asymptotic behavior of a generalized independent sets model on the two-dimensional Sierpinski gasket
- Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
- Quasirandom graphs and the pantograph equation
- Disagreement percolation for the hard-sphere model
- Long paths and connectivity in 1-independent random graphs
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- Analyticity for classical gasses via recursion
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
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)
