[Colloquium] Tom Hayes tal k 9/25 at TTI-C
Meridel Trimble
mtrimble at tti-c.org
Tue Sep 23 15:10:12 CDT 2003
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-Cs Conference Room (The Press Building - 1427 E. 60th St.)
Speakers 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)
More information about the Colloquium
mailing list