Skip to content

CSM

Seminar

Independent sets, lattice gases and the Loavsz Local Lemma

Scott, A (Oxford)
Thursday 24 January 2008, 10:00-11:00

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.

Audio

MP3MP3

Video

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.

Back to top ∧