[Colloquium] Tom Hayes tal k – 9/25 at TTI-C

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK

This Thursday at 12:15 pm, recent U of C alum Tom Hayes will give a talk at TTI-
C. Title and abstract below. LUNCH WILL BE PROVIDED.

Date: Thursday, September 25th, 2003
Time:  12:15 pm
Place: TTI-C’s Conference Room (The Press Building - 1427 E. 60th St.)
Speaker’s homepage: 
www.tti-c.org/hayes.shtml 
www.cs.uchicago.edu/~hayest

Title: Markov Chains for Randomly Coloring Graphs

Abstract: 
Consider the problem of generating a proper k-coloring of a given graph G, 
uniformly at random from all such colorings (adjacent vertices must receive 
different colors). When k is larger than the maximum degree of G, it is trivial 
to construct such a coloring via a greedy algorithm.  In sharp contrast, the 
problem of sampling such a coloring uniformly at random remains unsolved. 

Following the Markov Chain Monte Carlo approach, we study a very simple Markov 
chain on proper graph colorings, whose distribution tends asymptotically 
towards uniform. The chain is said to be ``rapidly mixing'' when the 
convergence time depends polynomially on the size of the graph.  It is widely 
conjectured that our simple chain is rapidly mixing whenever the number of 
colors exceeds the maximum degree. 

I will discuss partial results in this direction, especially those in my papers 
from STOC and FOCS 2003 (links below). The focus will be on recent advances in 
the coupling method, a general technique for proving rapid mixing. 

Links to papers: 
http://www.cs.uchicago.edu/~hayest/papers/GirthFive 
http://www.cs.uchicago.edu/~hayest/papers/NonMarkovianColorings

Please contact Meridel Trimble for further information 
(mtrimble at tti-c.org/773.834.9873)