skip to content

Independent sets, lattice gases and the Loavsz Local Lemma

Thursday 24th January 2008 - 10:00 to 11:00
INI Seminar Room 1

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.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons