Talks & Seminars
Randomly sampling graph colorings
Tom Hayes,
Date & Time: January 5, 2004 16:30
Venue: Seminar Hall
For a given graph $G$, and a positive integer $k$, we consider the problem of sampling proper $k$-colorings of $G$ almost-uniformly at random. When $k$ is larger than the maximum degree of $G$, there is a greedy algorithm for _constructing_ such a coloring in linear time. However, even with this many colors, it is not known whether colorings can be sampled nearly uniformly in polynomial time. We recently showed that, assuming $G$ has high girth and high maximum degree, that when $k > (1+\epsilon) \times$max degree, $k$-colorings can be sampled efficiently. The factor $(1+\epsilon)$ improves the previously best known factor 1.489..., which also required similar assumptions on the graph. The best known factor which does not require any assumptions on the graph is 11/6. The coloring algorithm we study is a very simple Markov chain on the space of proper graph colorings. This talk will focus on new extensions to the coupling technique for proving rapid "mixing" of such chains. This is joint work with Eric Vigoda of the University of Chicago. http://www.cs.uchicago.edu/~hayest also, http://www.tti-c.org/hayes.shtml
Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback