Personal tools
You are here: Home Events Abstract Archives 2000 Sampling Colourings and the Coupling Technique

Sampling Colourings and the Coupling Technique

Eric Vigoda LFCS, University of Edinburgh 4pm Tuesday 8 February 2000 Room 2511, JCMB, King's Buildings

Given a graph with maximum degree Delta, we are interested in sampling uniformly at random from the set of proper k-colorings of the graph. We design a simple Markov chain whose stationary distribution is the desired distribution and which quickly converges to its stationary distribution when k>11/6 Delta. The proof of convergence relies on a coupling argument, a well known technique in probability theory which has recently been useful in analyzing Markov Chain Monte Carlo algorithms. I'll give a thorough introduction to the coupling technique by explaining some previous work on this problem of Edinburgh's Mark Jerrum.

Document Actions