The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma (Q2487791): Difference between revisions

In this paper, a connection between equilibrium statistical mechanics and probabilistic combinatorics is exhibited and then used to reprove and extend interesting results in these fields. The system of statistical mechanics relevant for this is the repulsive lattice gas. Its partition function is identified to be a generalization of the usual independent-set polynomial. On the combinatorial side, the main statement of interest for this paper is the Lovasz local lemma, which provides a bound for the probability of absence of a set of dependent ``bad'' events in probabilistic combinatorics. It is shown that the bound in the Lovasz local lemma holds if and only if the independent-set polynomial is nonvanishing in a polydisc. The latter statement, in the formulation that the partition function of the lattice gas is nonvanishing at small activities, is usually proven by Mayer expansion methods. In this paper it is shown that the standard proof of the Lovasz local lemma corresponds to an argument by Dobrushin that proves nonvanishing of the partition function for the lattice gas in an inductive way which requires no explicit Mayer expansion. The connection to the lattice gas also allows for a generalization of the Lovasz local lemma to ``soft'' dependencies, corresponding to lattice gas interactions that are not hard-core. The paper is written so as to be accessible to readers that are familiar with only one of the two fields involved, hence it contains expositions of the essentials of either field, as well as many examples and interesting details, such as certain alternating-sign properties of the Mayer coefficients (some of which are new results).