DIMACS - Graduate Student Combinatorics Seminar

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.

See: http://math.rutgers.edu/~klm296/GCS/index.html