Friday, June 6, 2008 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
Random colorings of graphs
Speaker: | Juan Vera |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
We consider the problem of generating a colouring of the graph G uniformly at random using a natural Markov chain algorithm: the Glauber dynamics. We survey results on generating random colorings for general graphs and present improved results on random colorings of planar graphs.
Joint work with Nayantara Bhatnagar, Thomas Hayes and Eric Vigoda.