[Colloquium] How many colors are needed to randomly color a graph? A Markov chain approach

Watch Colloquium: 

AVI file (421 MB)
Quicktime (160 MB)

Thomas Hayes 
University of Chicago

Abstract: Markov chains are widely used to efficiently sample from complex distributions over sets of exponential size. They are at the heart of some of our best algorithms, e.g. for estimating the volume of high-dimensional convex bodies, estimating the permanent, and sampling configurations of the Ising model in statistical physics. An unusual feature of these algorithms is that their practical implementation relies crucially on a good theoretical understanding of the convergence rate of the underlying Markov chain: running the chain for too many steps wastes resources, but not running long enough produces the wrong output.

I will discuss some recent advances in the analysis of Markov chain Monte Carlo (MCMC) algorithms, using the following problem as a touchstone example.

A (proper) coloring of a graph is an assignment of a color to each vertex so that no two adjacent vertices receive the same color.  Assuming the number of colors is at least D+1, where D is the maximum degree of the graph, a simple greedy algorithm produces such a coloring in linear time.  But suppose we want to efficiently produce not just any coloring, but rather a typical (i.e., uniformly random) coloring.  How many colors do we need now?

Here is a very simple MCMC algorithm: start with any coloring, for instance one obtained by the greedy algorithm. In each step, recolor a randomly chosen vertex with a randomly chosen color, subject to the constraint that adjacent vertices cannot be assigned the same color.  It is not hard to see that, given enough colors, this algorithm generates a nearly-uniform random coloring in nearly-linear time.  The problem is: how many colors are “enough”?

I will give an overview of recent advances on this problem, each based on extensions of the classical “coupling” method for analyzing Markov chain convergence.