# CSM

## Seminar

### Independent sets, lattice gases and the Loavsz Local Lemma

Seminar Room 1, Newton Institute

#### Abstract

The repulsive lattice gas is an important model in equilibrium statistical mechanics, and has been studied extensively by mathematical physicists. In the special case of a hard-core nearest-neighbor exclusion (i.e. no pair of adjacent sites can be simultaneously occupied), the partition function of the lattice gas on a graph coincides with the independent-set polynomial. Much effort has been devoted to finding regions in the complex plane in which this function is nonvanishing

The Lovasz Local Lemma is a valuable tool in probabilistic combinatorics for estimating the probability that none of a collection of "bad" events occurs. It applies when dependence between events can be controlled by a "dependency graph", and is useful when the graph is very sparse.

In this talk, which presents joint work with Alan Sokal, I will examine a connection between these two apparently disparate subjects. I will discuss closely related results of Shearer in probabilistic combinatorics and of Dobrushin in mathematical physics, as well as a "soft" generalization of the Lovasz Local Lemma.

## Comments

Start the discussion!