Independent sets, lattice gases and the Loavsz Local Lemma

1 hour 9 mins 31 secs, 961.97 MB, MPEG-4 Video 480x360, 25.0 fps, 44100 Hz, 1.84 Mbits/sec

About this item

Description:	Scott, A (Oxford) Thursday 24 January 2008, 10:00-11:00 Zeros of Graph Polynomials

Created:

2008-02-07 15:31

Collection:

Combinatorics and Statistical Mechanics

Publisher:

Isaac Newton Institute

Scott, A

Language:

eng (English)

Credits:

Author:

Scott, A


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.

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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video *	480x360	1.84 Mbits/sec	961.97 MB	View	Download
Flash Video	480x360	806.34 kbits/sec	411.14 MB	View	Download
iPod Video	480x360	505.27 kbits/sec	257.63 MB	View	Download
Windows Media Video (for download)	480x360	477.26 kbits/sec	243.35 MB	View	Download
Windows Media Video (for streaming)	480x360	447.94 kbits/sec	228.40 MB	View	Download	Stream
RealMedia	480x360	877.71 kbits/sec	447.54 MB	View	Download	Stream
QuickTime (for download)	384x288	848.71 kbits/sec	432.75 MB	View	Download
QuickTime (for streaming)	480x360	907.12 kbits/sec	462.53 MB	View	Download
MP3	44100 Hz	125.01 kbits/sec	63.53 MB	Listen	Download