Event Detail

Event Type: 
Department Colloquium
Friday, February 15, 2008 - 08:00
Kidd 364

Speaker Info

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 and signed graphs, a counting function for magic squares, Ehrhart polynomials enumerating integer points in polytopes, and characteristic polynomials of hyperplane arrangements.