The Repulsive Lattice Gas, the Independent-Set Polynomial, and the Lovász Local Lemma

By A. Scott, Alan D. Sokal. 2003

244 citations recorded by the source corpus.

We elucidate the close connection between the repulsive lattice gas in equilibrium statistical mechanics and the Lovász local lemma in probabilistic combinatorics. We show that the conclusion of the Lovász local lemma holds for dependency graph G and probabilities {px} if and only if the independent-set polynomial for G is nonvanishing in the polydisc of radii {px}. Furthermore, we show that the usual proof of the Lovász 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(98) and explicitly by Dobrushin.(37,38) We also present some refinements and extensions of both arguments, including a generalization of the Lovász 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.

Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/292f5ea6d6915fa912540e9d602f0e9aac051aad

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

The multivariate Tutte polynomial (alias Potts model) for graphs and matroids (2005, background): “erties of the spanning-tree polynomial and its generalization to matroids. 17These results are, in turn, closely related to the Lov´asz local lemma [55,56,124,125] in probabilistic combinatorics; see [114] for a detailed development of this connection. 18The intersection graph of a ﬁnite set S is th”
Counting independent sets up to the tree threshold (2006, background): “Also, after completing this manuscript the author has learned that a tree equivalent to Tsaw(G, v) has already appeared in [20], though in a somewhat different context and without suggesting the kind of result established in Theorem 2.”
The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability (2008, background): “Characterize all linear operators T : Kκ[z1, . . . , zn] → K[z1, . . . , zn] that preserve Ω-stability for a given set Ω ⊂ Cn and κ ∈ Nn. Problem 2.”