Mathematics Colloquium: Combinatorial Reciprocity Theorems

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.

Time: Friday, August 29, 2014, 3:30-4:20 p.m.

Place: Exploratory Hall, room 4106

Refreshments will be served at 3:00 p.m.