skip to content

Random colorings

Tuesday 25th March 2008 - 10:00 to 11:00
INI Seminar Room 1

I will give a survey of results on the analysis of MCMC algorithms for randomly sampling proper vertex k-colorings of an input graph with maximum degree D. In the first part of the talk I will explain how such a sampling algorithm implies an algorithm to estimate the number of k-colorings. The standard reduction considers the problem at a sequence of temperatures, where the infinite temperature problem corresponds to colorings of the empty graph and the zero temperature problem corresponds to colorings of the input graph. I will present recent work (with Stefankovic and Vempala) that reduces the number of intermediate temperatures in this reduction to O*(\sqrt{n}).

After the briefest introduction to coupling, I'll show Jerrum's proof of fast convergence of the single-site Glauber dynamics for any graph when k>2D. We'll then look at more sophisticated coupling arguments, beginning with the work of Dyer and Frieze, that utilize so-called local uniformity properties, which are local properties of random colorings. I'll then explain more recent work of Hayes that utilizes the spectral radius to get improved results for colorings of planar graphs. Finally, we'll see recent work (with Hayes and Vera) that combines the uniformity and spectral radius ideas to prove poly-time convergence of the Glauber dynamics on planar graphs when k>D/logD.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons