Algebraic Combinatorics Seminar
####
**
UNIVERSITY OF KENTUCKY **

ALGEBRAIC COMBINATORICS SEMINAR

945 PATTERSON OFFICE TOWER

SPRING 2005

####

##
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).