×

zbMATH — the first resource for mathematics

On dependency graphs and the lattice gas. (English) Zbl 1138.05323
Summary: 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 \(\{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 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 [Combinatorica 5, 241–245 (1985; Zbl 0587.60012)] and explicitly by R. Dobrushin [Topics in statistical and theoretical physics. Transl., Ser. 2, Am. Math. Soc. 177(32), 59–81 (1996; Zbl 0873.60074), Lect. Notes Math. 1648, 1–66 (1996; Zbl 0871.60086)]. We also present a generalization of the Lovász Local Lemma that allows for ‘soft’ dependencies.
The paper aims to provide an accessible discussion of these results, which are drawn from a longer paper [J. Stat. Phys. 118, No. 5–6, 1151–1261 (2005; Zbl 1107.82013)].

MSC:
05C80 Random graphs (graph-theoretic aspects)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI