Speaker: Matt Beck, San Francisco State University
Combinatorial Reciprocity Theorems
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
Tel. 703-993-1460, Fax. 703-993-1491