Inside-out polytopes and a tale of seven polynomialsAlgebra & Discrete Mathematics
|Speaker:||Matthias Beck, San Francisco State University|
|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).