Combinatorial Reciprocity Theorems

Start: 04/09/2008 - 3:15pm
End  : 04/09/2008 - 4:15pm


Mathias Beck (San Francisco State University)


A common theme of enumerative combinatorics are counting functions given
by polynomials that are evaluated at positive integers. 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. Combinatorial reciprocity theorems give interpretations
of these polynomials at negative integers. 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 coherent cycle.

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. We follow a common thread of chromatic and flow polynomials of
graphs, the Euler characteristic of polyhedra, Ehrhart polynomials
enumerating integer points in polytopes, and characteristic polynomials of
hyperplane arrangements.

Beckman Auditorium, B126, Harvey Mudd College