Title: Approximately Counting Graph Colorings
Speaker: Cole Franks, Rutgers University
Date: Wednesday, March 23, 2016 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
It is easy to see that a graph of degree d>0 has a proper 2d-coloring, but is it easy to count the number of such colorings? It turns out that in order to approximately count said colorings, it is enough to sample them (almost) uniformly at random. We`ll see why this is the case and go on to find an efficient way to sample these colorings using rapidly mixing Markov chains.