Skip to content

CSM

Seminar

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Sly, A (UC Berkeley)
Wednesday 26 March 2008, 10:35-11:05

Seminar Room 1, Newton Institute

Abstract

We overcome an obstacle of most techniques for analysing the mixing time of the Glauber dynamics, that they are stated in terms of the maximal degree and are therefore insufficient for Erdos Renyi random graphs where the maximum degree grows as order (log n)/(log log n). We show that for most natural models defined on G(n,d/n) if the "temperature" is high enough (as a function of d only) then the mixing time of Glauber dynamics is polynomial. This proves in particular a conjecture of Dyer et.al. proving rapid mixing of random colourings on G(n,d/n) with a constant number of colours.

Presentation

[pdf ]

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 ∧