|DATE:||Wednesday, February 2nd|
|TIME:||4:30 PM - 5:30 PM|
|TITLE:||The mixing rate of the Glauber dynamics on graph colourings|
|SPEAKER:||Mike Molloy, Dept of Computer Science, University of Toronto|
Thus, this particular chain can be used to generate a random colouring of a graph which is very close to being from the uniform distribution.
Jerrum showed that for a graph on n vertices with maximum degree D, this chain mixes in O(n log n) time, as long as the number of colours is at least 2D+1. Here we prove the same bound when the number of colours is at least (2-x)D for a small constant x>0.
This includes some joint work with M. Dyer and C. Greenhill.