Combinatorial Applications of Ehrhart Theory, Hypergraph Coloring Complexes and the Ehrhart f*-vector
Speaker: Felix Breuer
Date: 12/12/2012
Time: 14:00 - 16:00
Time: 14:00 - 16:00
Location: HS12 (TNF,JKU)
The Ehrhart function of a set X in Euclidean space counts the number of integer points in the k-th dilate of X. If X is a polytope with integral vertices, the Ehrhart function of X coincides with a polynomial at all positive integers k. This polynomial is called the Ehrhart polynomial of X and its h*- and f*- vectors are coefficient vectors with respect to certain binomial bases of the space of polynomials. Ehrhart theory offers several nice results about these polynomials, from bounds on their coefficients to geometric interpretations of their values at negative integers. In recent years, Ehrhart theory has found a number of applications in combinatorics. The idea is to model combinatorial counting functions as Ehrhart functions of suitable geometric objects and then apply theorems from Ehrhart theory to obtain results. I will begin this talk by giving an overview of some of these applications of Ehrhart theory in combinatorics, dealing with chromatic polynomials, flow polynomials and tension polynomials of graphs. These examples motivate the study of hypergraph coloring complexes and I will present some results about hypergraph coloring complexes in greater detail. One interesting fact is that these complexes do not, in general, have a non-negative Ehrhart h*-vector, while their f*-vector, on the other hand, is always non-negative. It turns out that this is no accident: Ehrhart f*-vectors of polytopal complexes are always non-negative, even if the complex is non-convex and does not have a unimodular triangulation. Moreover, the f*-coefficients of Ehrhart polynomials have a concrete counting interpretation. An interesting corollary is that this property characterizes Ehrhart polynomials of partial polytopal complexes: A polynomial is the Ehrhart polynomial of some partial polytopal complex if and only if its f*-vector is non-negative.