Hypergraph Coloring Complexes and the Ehrhart f*-vectorAlgebra & Discrete Mathematics
|Felix Breuer, San Francisco State University
|Thu, Mar 22 2012, 3:10PM
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. 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. In this talk, we will examine the chromatic polynomial of hypergraphs from an Ehrhart perspective. This approach leads naturally to hypergraph coloring complexes. 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. (Ehrhart h*- and f*-vectors are coefficient vectors of Ehrhart polynomials with respect to certain natural binomial bases of the space of polynomials that are closely related to h- and f-vectors of simplicial complexes.) It turns out that this is no accident: Ehrhart f*-vectors of polytopal complexes are always non-negative, even if the complex does not have a unimodular triangulation. A sketch of the proof of this theorem will conclude my talk.