Speaker: Matt Beck, San Francisco State University
Title:
Combinatorial Reciprocity Theorems
Abstract:
A common theme of enumerative combinatorics is formed by counting functions
that are polynomials.
For example, one proves in any introductory graph theory course
that the number of proper k-colorings of a given graph G is a polynomial in k, the
chromatic polynomial of G. Combinatorics is abundant with polynomials that count
something when evaluated at positive integers, and many of these polynomials have
a (completely different) interpretation when evaluated at negative integers: these
instances go by the name of combinatorial reciprocity theorems. For example, when
we evaluate the chromatic polynomial of G at -1, we obtain (up to a sign) the number
of acyclic orientations of G, that is, those orientations of G that do not contain
a coherently oriented cycle.
Reciprocity theorems appear all over combinatorics. This talk will attempt to show
some of the charm (and usefulness!) these theorems exhibit. Our goal is to weave
a unifying thread through various combinatorial reciprocity theorems, by looking
at them through the lens of geometry.
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