Felix Breuer's Blog

Ehrhart f*-coefficients of polytopal complexes are non-negative integers

One week ago, my most recent math paper appeared on the arXiv and now I finally get around to blogging about it.

The \(f^*\)- and \(h^*\)-coefficents of a polynomial \(p(k)\) are simply the coefficients of \(p(k)\) with respect to certain binomial bases of the space of polynomials. If \(p\) is of degree \(d\), then they are given by \[p(k)=\sum_{i=0}^d f^*_i {k-1 \choose i} =\sum_{i=0}^d h^*_i {k+d-i \choose d}.\]

Where do these definitions come from? The motivation is Ehrhart theory. Given a set \(X\subset\mathbb{R}^d\), the Ehrhart function \(L_X\) of \(X\) is given by \[L_X(k)=\#\mathbb{Z}^d\cap k\cdot X,\] for \(1\leq k \in \mathbb{Z}\), that is, \(L_X(k)\) counts the number of integer points in the \(k\)-th dilate of \(X\).

Now, a famous theorem by Ehrhart states that if \(X\) is a polytope with integral vertices, then \(L_X\) is a polynomial. More precisely, there exists a polynomial that coincides with \(L_X\) at all positive integers and by abuse of notation, we will denote this polynomial by \(L_X\) as well.

After this preamble you may already have guessed it. The binomials in the expansion above are Ehrhart polynomials of particularly nice polytopes, namely half-open unimodular simplices. We denote by \(\Delta^d_i\) the \(d\)-dimensional standard simplex with \(i\)-open faces, i.e., \[\Delta^d_i = \{ x\in\mathbb{R}^{d+1} \;|\; x_0,\ldots,x_{i-1} > 0, x_i,\ldots x_d\geq 0 \sum_{i=0}^d x_i = 1 \} \]

and then it is not hard to check that \[L_{\Delta^d_i}(k) = {k+d-i \choose d}\] and in particular \[L_{\Delta^d_{d+1}}(k) = {k-1\choose d}.\] Thus:

  • If \(P\) is a lattice polytope with a shellable unimodular triangulation \(K\), then \(h^*_i\) counts the number of \(d\)-dimensional simplices with \(i\) open faces in a shelling of \(K\).
  • If \(P\) is a lattice polytope with a unimodular triangulation \(K\), then \(f^*_i\) counts the number of \(i\)-dimensional faces in \(K\).

In particular, if \(P\) is sufficiently nice, then both the \(f^*\)- and the \(h^*\)-coefficients are non-negative. The point of my article is to show that even if \(P\) is not nice and partitioning \(P\) into unimodular simplices does not work at all, the \(f^*\)-vector is still non-negative.

Theorem. If \(P\) is a polytopal complex, then the \(f^*\)-coefficients of \(L_P\) are non-negative integers, even if \(P\) does not have a unimodular triangulation.

This becomes relevant when \(P\) is not-convex. As long as \(P\) is a polytope, its \(h^*\)-coefficients are non-negative by a famous theorem of Stanley. However, the \(h^*\)-coefficients of polytopal complexes may well be negative. For example, in recent work, Martina Kubitzke, Aaron Dall and myself have shown that there exist coloring complexes of hypergraphs with negative \(h^*\)-coefficents.

In fact, we can take this theorem one step further and use it to characterize Ehrhart polynomials of what I call partial polytopal complexes. An integral partial polytopal complex is any set in \(\mathbb{R}^d\) that can be written as the disjoint union of relatively open polytopes with integral vertices.

Theorem. A vector is the vector of \(f^*\)-coefficients of some integral partial polytopal complex if and only if it is integral and non-negative.

Behind all of this lies a combinatorial interpretation of the \(f^*\)-coefficients in a (not necessarily unimodular) lattice simplex and a new way of partitioning the set of lattice points in a simplicial cone into discrete cones.

For more results, in particular about the rational case, and more details on all of this, please check out my article! It has the id arxiv: 1202.2652.