Inside-out polytopes and a tale of seven polynomials

Professor Matthias Beck
San Francisco State University

Monday, April 4, 2005
4 pm, 945 Patterson Office Tower

Abstract:

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 generalizations 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öbius 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 interpretation is in some examples a mystery.

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