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

DOI10.1007/s10955-004-2055-4zbMath1107.82013arXivcond-mat/0309352OpenAlexW2157869188WikidataQ56893206 ScholiaQ56893206MaRDI QIDQ2487791

Alan D. Sokal, Alexander D. Scott

Publication date: 8 August 2005

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

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

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)

Related Items (81)

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

Cites Work

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

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