Speaker: Yvonne Kemper, National Institute of Standards and Technology
Title:
From Broken Circuits to Monte Carlo: Approximating
the Coefficients of the Chromatic Polynomial
Abstract: Chromatic polynomials are fascinating objects that tie together graph theory and statistical physics, and their study brings together matroids, geometry, monomial rings, and more. As a result of computational difficulties, however, their study is limited to graphs that are small, highly structured, or very sparse. We have devised and implemented algorithms that approximate the coefficients of the chromatic polynomial P(G,x). In this (friendly!) talk, we will discuss previous approximation algorithms, the combinatorial and geometric bases for our algorithms, and possibilities for improvement, including proving bounds on variance.
Time: Friday, February 20, 2015, 3:30-4:20 p.m.
Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491