GEORGE MASON UNIVERSITY
DEPARTMENT OF MATHEMATICAL SCIENCES
COLLOQUIUM
FEBRUARY 20, 2015


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.

Place: Exploratory Hall, room 4106

Refreshments will be served at 3:00 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