skip to content

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

Presented by: 
A Sly [UC Berkeley]
Wednesday 26th March 2008 - 10:35 to 11:05
INI Seminar Room 1

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 proving rapid mixing of random colourings on G(n,d/n) with a constant number of colours.

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.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons