The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



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


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.


[pdf ]




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 ∧