McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.

DATE:	Wednesday, February 2nd
TIME:	4:30 PM - 5:30 PM
PLACE:	McConnell 320
TITLE:	The mixing rate of the Glauber dynamics on graph colourings
SPEAKER:	Mike Molloy, Dept of Computer Science, University of Toronto

We discuss a natural and well-studied Markov chain on the colourings of a fixed graph. The usual goal, when studying such chains, is to try to show that they mix very quickly. What this means is that if you run the Markov chain from any initial state, within a short period of time, it's state will be very close to uniformly random.

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at cgm-help@cgm.cs.mcgill.ca.