Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Inside-out polytopes and a tale of seven polynomials

Algebra & Discrete Mathematics

Speaker: Matthias Beck, San Francisco State University
Location: 693 Kerr
Start time: Fri, Feb 18 2005, 12:10PM

We study lattice-point counting in polytopes with boundary on the inside. To say this in a less mysterious way: we consider a convex polytope P together with an arrangement of hyperplanes that dissects the polytope, and we count points of a discrete lattice, such as the integer lattice, that lie inside of P but not on any of the hyperplanes. Our counting functions are generaliztions of Ehrhart polynomials (which one obtains in the absence of the hyperplane arrangement).

Our first purpose is to encompass colorings and acyclic orientations of graphs and signed graphs within the framework of counting lattice points in polytopes. Our second purpose is to apply the same framework to a multitude of counting problems in which there are forbidden values or relationships amongst the values of an integral function on a finite set: nowhere-zero integral flows, magic, antimagic, and latin squares, magic and antimagic graphs, and generalizations involving rational linear forms. Another interesting phenomenon is the relationship between the point count and the characteristic polynomial of the arrangement. Our results are of three kinds: quasipolynomiality of counting functions, M\"obius inversion formulas, and the appearance of quantities that parallel Stanley's theorem on the evaluation of the chromatic polynomial at negative integers but whose combinatorial inter pretation is in some examples a mystery.

This is joint work with Tom Zaslavsky (Binghamton University, SUNY).