Abstract

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.