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
- 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)- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- An algorithmic proof of the Lovász local lemma via resampling oracles
- Computing the partition function for graph homomorphisms with multiplicities
- Implementations and the independent set polynomial below the Shearer threshold
- The bipermutahedron
- Covering systems with restricted divisibility
- One-dependent colorings of the star graph
- Homomorphisms from the torus
- The Ising partition function: zeros and deterministic approximation
- Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs
- Asymptotic behavior of a generalized independent sets model on the two-dimensional Sierpinski gasket
- An asymptotic formula for the zeros of the deformed exponential function
- Shearer's point process, the hard-sphere model, and a continuum Lovász local lemma
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- 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
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- 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
- Partially independent random variables
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- Cayley trees do not determine the maximal zero-free locus of the independence polynomial
- Absence of zeros implies strong spatial mixing
- Gauges, loops, and polynomials for partition functions of graphical models
- On independent sets in graphs with given minimum degree
- Improved bounds on coloring of graphs
- The method of cumulants for the normal approximation
- On a conjecture of Sokal concerning roots of the independence polynomial
- The independence polynomial of rooted products of graphs
- The Lee--Yang and Pólya--Schur programs. I: Linear operators preserving stability
- Zeros of the deformed exponential function
- Fundamentals of partial rejection sampling
- Long paths and connectivity in 1-independent random graphs
- A proof of the upper matching conjecture for large graphs
- Independent sets in the hypercube revisited
- 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
- Proof of the Kalai-Meshulam conjecture
- On the zeroes of hypergraph independence polynomials
- Benjamini-Schramm continuity of root moments of graph polynomials
- Independence polynomials and hypergeometric series
- Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
- Bounds For The Real Zeros of Chromatic Polynomials
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- Cluster expansion for abstract polymer models. New bounds from an old approach
- Disagreement percolation for the hard-sphere model
- An improvement of the Lovász local lemma via cluster expansion
- The Blume-Emery-Griffiths model on the FAD point and on the AD line
- Transversals in generalized Latin squares
- Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
- 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
- Approximating real-rooted and stable polynomials, with combinatorial applications
- Approximating permanents and hafnians
- Correlation decay and the absence of zeros property of partition functions
- Generalizations of the matching polynomial to the multivariate independence polynomial
- A generalization of Schönemann's theorem via a graph theoretic method
- Cluster expansion in the canonical ensemble
- Algorithmic Pirogov-Sinai theory
- Cluster expansions for Gibbs point processes
- Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
- Inapproximability of the independent set polynomial in the complex plane
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- Analyticity for classical gasses via recursion
- Cluster expansions: necessary and sufficient convergence conditions
- Quasirandom graphs and the pantograph equation
- On the number of \(r\)-matchings in a tree
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- Algorithms for \#BIS-hard problems on expander graphs
- Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion
- On the convergence of cluster expansions for polymer gases
- Fisher zeros and correlation decay in the Ising model
- Sufficient conditions for uniform bounds in abstract polymer systems and explorative partition schemes
- Note on the smallest root of the independence polynomial
- The bivariate Ising polynomial of a graph
- Fisher Zeros and Correlation Decay in the Ising Model
- Finitely dependent coloring
- Convergence of cluster and virial expansions for repulsive classical 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)
