# Viewing counting polynomials as Hilbert functions via Ehrhart theory

Felix Breuer<fnref n="1" />†and Aaron Dall<fnref n="2" />

**Abstract.**

Steingrímsson (2001) showed that the chromatic polynomial of a graph is the Hilbert function of a relative Stanley-Reisner ideal. We approach this result from the point of view of Ehrhart theory and give a sufficient criterion for when the Ehrhart polynomial of a given relative polytopal complex is a Hilbert function in Steingrímsson's sense. We use this result to establish that the modular and integral flow and tension polynomials of a graph are Hilbert functions.

**Résumé.** Steingrímsson (2001) a montré que le polynôme chromatique d'un graphe est la fonction de Hilbert d'un idéal relatif de Stanley-Reisner. Nous abordons ce résultat du point de vue de la théorie d'Ehrhart et donnons un critère suffisant pour que le polynôme d'Ehrhart d'un complexe polytopal relatif donné soit une fonction de Hilbert au sens de Steingrímsson. Nous utilisons ce résultat pour établir que les polynômes de flux et de tension modulaires et intégraux d'un graphe sont des fonctions de Hilbert.

**Keywords:** Hilbert function, lattice polytope, relative Stanley-Reisner ring, tension polynomial, flow polynomial, relative polytopal complex

# 1 Introduction

Steingrímsson [Ste01] showed that the proper $k+1$-colorings of a graph $G$ are in bijection with the monomials of degree $k$ in a polynomial ring $K[x_1, \dots, x_n]$ that lie inside a square-free monomial ideal $I_2$, but outside a square-free monomial ideal $I_1$. In other words, he showed that the chromatic polynomial $\chi_G$ of $G$ is the Hilbert function of a relative Stanley-Reisner ideal. To this end, he used a clever combinatorial construction to describe the ideals $I_1$ and $I_2$ explicitly.

In this article we approach the problem from the point of view of Ehrhart theory, which allows us to arrive quickly at a sufficient criterion for when the Ehrhart polynomial of a given relative polytopal complex is a Hilbert function in Steingrímsson's sense:

> The Ehrhart function of a relative polytopal complex in which all faces are compressed is the Hilbert function of a relative Stanley-Reisner ideal.

<footnote n="1">¹Freie Universität Berlin, Arnimallee 3, 14195 Berlin, Germany, felix.breuer@fu-berlin.de</footnote>

<footnote n="2">²adall1979@gmail.com</footnote>

<footnote>†Supported by the DFG research training group “Methods for Discrete Structures” (GrK 1408).</footnote>
See Theorem 5. We then apply this general result to establish that four other counting polynomials defined in terms of graphs are Hilbert functions: the modular flow and tension polynomials and their integral variants. Also, we are able to improve Steingrímsson's result insofar as we are able to obtain the chromatic polynomial $\chi_G(k)$ itself as a Hilbert function, and not only the shifted chromatic polynomial $\chi_G(k+1)$. We conclude the paper by giving another more algebraic proof of our geometric theorem, which allows us to generalize the result further.

These results have been developed in the authors' respective theses [Dal08] and [Bre09], to which we refer the interested reader for further details and additional material.

This paper is organized as follows. After some preliminary definitions in Section 2 we review Steingrímsson's theorem and related work in Section 3. In Section 4 our main result is derived. In Section 5 we apply this result to show that all five counting polynomials are Hilbert functions. We present a generalization of our main result in Section 6 along with a more algebraic proof. Finally, we give some constraints on the coefficients of the polynomials and discuss questions for further research in Section 7.

## 2 Preliminary Definitions

Before we begin, we gather some definitions. We recommend the textbooks [BR07, MS05, Sta96, Sch86] as references.

The **Ehrhart function** $L_A$ of any set $A \subset \mathbb{R}^n$ is defined by $L_A(k) = |\mathbb{Z}^n \cap k \cdot A|$ for $k \in \mathbb{N}$. A **lattice polytope** is a polytope in $\mathbb{R}^n$, such that all vertices are integer points. It is a theorem of Ehrhart that the Ehrhart function $L_P(k)$ of a lattice polytope is a polynomial in $k$. Two polytopes $P, Q$ are **lattice isomorphic**, $P \approx Q$, if there exists an affine isomorphism $A$ such that $A|_{\mathbb{Z}^n}$ is a bijection onto $\mathbb{Z}^n$ and $AP = Q$. A $d$-**simplex** is the convex hull of $d+1$ affinely independent points. A $d$-simplex is **unimodular** if it is lattice isomorphic to the convex hull of $d+1$ standard unit vectors. A lattice polytope is **empty** if the only lattice points it contains are its vertices. A **hyperplane arrangement** is a finite collection $\mathcal{H}$ of affine hyperplanes and $\bigcup \mathcal{H}$ denotes the union of all of these.

A **polytopal complex** is a finite collection $\mathcal{C}$ of polytopes in some $\mathbb{R}^n$ with the following two properties: If $P \in \mathcal{C}$ and $F$ is a face of $P$, then $F \in \mathcal{C}$; and if $P, Q \in \mathcal{C}$ then $F = P \cap Q \in \mathcal{C}$ and $F$ is common face of both $P$ and $Q$. The polytopes in $\mathcal{C}$ are also called **faces** and $\bigcup \mathcal{C}$ denotes the union of all faces of $\mathcal{C}$. A (geometric) **simplicial complex** is a polytopal complex in which all faces are simplices. An **abstract simplicial complex** is a set $\Delta$ of subsets of a finite set $V$, such that $\Delta$ is closed under taking subsets. A geometric simplicial complex $\Delta$ gives rise to an abstract simplicial complex $\text{comb}(\Delta)$ via $\text{comb}(\Delta) = \{\sigma|\sigma$ is the vertex set of some $F \in \mathcal{C}\}$. A polytopal complex $\mathcal{C}'$ that is a subset $\mathcal{C}' \subset \mathcal{C}$ of a polytopal complex $\mathcal{C}$ is called a **subcomplex** of $\mathcal{C}$. Subcomplexes of abstract simplicial complexes are defined similarly. Given a collection $S$ of polytopes in $\mathbb{R}^n$ such that for any $P, Q \in S$ the set $P \cap Q$ is a face of both $P$ and $Q$, the polytopal complex $\mathcal{C}$ **generated by** $S$, is $\mathcal{C} = \{F|F$ a face of $P \in S\}$. A **subdivision** of a polytopal complex $\mathcal{C}$ is a polytopal complex $\mathcal{C}'$ such that $\bigcup \mathcal{C}' = \bigcup \mathcal{C}$ and every face of $\mathcal{C}'$ is contained in a face of $\mathcal{C}$. A **triangulation** is a subdivision in which all faces are simplices. A **unimodular triangulation** is a triangulation in which all simplices are unimodular.

Let $\mathbb{K}[x] = \mathbb{K}[x_1, \dots, x_n]$ denote the polynomial ring in $n$ variables over some field $\mathbb{K}$ equipped with the standard grading by degree $\mathbb{K}[x] = \bigoplus_{k \ge 0} R_k$, where $R_k$ is the $\mathbb{K}$-vector space generated by all monomials of degree $k$. A **graded $\mathbb{K}[x]$-module** is a module $M$ that can be written as a direct sum of abelian groups $M = \bigoplus_{-\infty}^{\infty} M_k$ such that $R_i M_j \subset M_{i+j}$ for all $i$ and $j$. The **Hilbert function** $\text{H}_M$ of $M$ is defined by $\text{H}_M(k) = \dim_{\mathbb{K}} M_k$. Let $I_1$ be a monomial ideal in $\mathbb{K}[x]$ and consider the quotient ring
$K[x]/I_1$ graded by degree. Then $H_{K[x]/I_1}(k) = |\{x^a \in K[x] | x^a \notin I_1, \deg(x^a) = k\}|$. Furthermore let $I_2 \supset I_1$ be another monomial ideal. By abuse of notation we also denote by $I_2$ the ideal in $K[x]/I_1$ generated by the same set of monomials. We can write $I_2 = \bigoplus_{k \ge 0} I_2^k$ where $I_2^k$ is the vector space generated by the monomials $x^a$ in $I_2$ with $\deg(x^a) = k$ that are non-zero in $K[x]/I_1$. Then $R_i I_2^k \subset I_2^{i+k}$, where the product is taken in $K[x]/I_1$, and $H_{I_2}(k) = |\{x^a \in I_2 \setminus I_1 | \deg(x^a) = k\}|$. A term order on $K[x]$ is a total order on the monomials $x^a \in K[a]$ such that $1 < x^a$ for all $a \in \mathbb{Z}_{\ge 0}^n$ and $x^a < x^b$ implies $x^{a+c} < x^{b+c}$ for all $a, b, c \in \mathbb{Z}_{\ge 0}^n$.

We consider oriented graphs that may have loops and multiple edges. Note, however, that the values of the five counting polynomials do not depend on the orientation of the graph and are thus invariants of the underlying unoriented graph. Formally, a **graph** is a tuple $(V, E, \text{head}, \text{tail})$, where $V$ is a finite vertex set, $E$ is a finite edge set and head : $E \to V$ and tail : $E \to V$ are maps. Graph theoretic concepts such as adjacency, paths, connectivity, etc. are defined in the usual way. We note that a cycle in the underlying unoriented graph can be coded as a map $c : E \to \{0, \pm 1\}$ where $c_e = +1$ if the direction in which $e$ is traversed is consistent with the orientation of $e$ in $G$, $c_e = -1$ if the direction of traversal is opposite to the orientation in $G$ and $c_e = 0$ if $e$ does not lie on the cycle. Here we view $c$ both as a map and as a vector as we shall do with all maps defined in this article. Let $k \in \mathbb{Z}_{\ge 0}$. A k-coloring of $G$ is a map $x : V \to \{0, \dots, k-1\}$ and it is called proper if $x_v \neq x_u$ whenever $u \sim v$. The chromatic polynomial $\chi_G$ is defined such that $\chi_G(k)$ is the number of proper k-colorings of $G$.

A k-tension of $G$ is a map $t : E \to \{-k+1, \dots, k-1\}$ such that

$$ \sum_{e \in E} c_e t_e = 0 \quad \text{for every cycle } c \text{ in } G. \qquad (1) $$

Similarly, a $\mathbb{Z}_k$-tension of $G$ is a map $t : E \to \mathbb{Z}_k$ such that (1) holds in $\mathbb{Z}_k$. A tension is **nowhere zero** if $t(e) \neq 0$ for all $e \in E$. Now we define functions $\theta_G$ and $\bar{\theta}_G$ as follows: $\theta_G(k)$ is the number of nowhere zero k-tensions of $G$ and $\bar{\theta}_G(k)$ is the number of nowhere zero $\mathbb{Z}_k$-tensions of $G$. Both $\theta_G(k)$ and $\bar{\theta}_G(k)$ are polynomials in $k$, called the **integral** and the **modular tension polynomial**, respectively.

A k-flow of $G$ is a map $f : E \to \{-k+1, \dots, k-1\}$ such that

$$ \sum_{\substack{e \in E \\ \text{head}(e)=v}} f_e - \sum_{\substack{e \in E \\ \text{tail}(e)=v}} f_e = 0 \quad \text{for every vertex } v \text{ of } G. \qquad (2) $$

Similarly, a $\mathbb{Z}_k$-flow of $G$ is a map $f : E \to \mathbb{Z}_k$ such that (2) holds in $\mathbb{Z}_k$. The functions $\varphi_G$ and $\bar{\varphi}_G$ are defined as follows: $\varphi_G(k)$ is the number of nowhere zero k-flows of $G$ and $\bar{\varphi}_G(k)$ is the number of nowhere zero $\mathbb{Z}_k$-flows of $G$. Both $\varphi_G(k)$ and $\bar{\varphi}_G(k)$ are polynomials in $k$, called the **integral** and the **modular flow polynomial**, respectively. More about these polynomials can be found in [BZ06a, BZ06b, Koc02, Bre09].

## 3 Steingrímsson's theorem and related work

Steingrímsson [Ste01] showed that for any graph $G$ the chromatic polynomial $\chi_G(k+1)$ shifted by one is the Hilbert function of a module with a particular structure.

**Theorem 1** (Steingrímsson [Ste01, Theorem 9]) For any graph $G$, there exists a number $n$, a square-free monomial ideal $I_1$ in the polynomial ring over $n$ variables $K[x] = K[x_1, \dots, x_n]$ and a square-free
monomial ideal $I_2$ in $\mathbb{K}[X]/I_1$ such that

$$H_{I_2}(k) = \chi_G(k+1)$$

for all $k \in \mathbb{Z}_{>0}$, where $H_{I_2}$ denotes the Hilbert function of $I_2$ with respect to the standard grading and $\chi_G$ denotes the chromatic polynomial of $G$.

In [Ste01] Steingrímsson went on to define the coloring complex of a graph to be the simplicial complex given by the square-free monomial ideal $I_2$. In the case of colorings the ideal $I_1$ has a simple description, so bounds on the $f$-vector of the coloring complex translate into bounds on the coefficients of the chromatic polynomial. The articles [Jon05, Hul07, HS08], building on Steingrímsson's work, have mainly dealt with showing various properties of the coloring complex. Steingrímsson himself gave a combinatorial description of the coloring complex and determined its Euler characteristic to be the number of acyclic orientations of $G$. To some extent this was already known: Welker observed that the coloring complex of a graph $G = (V, E)$ is the same as a complex appearing in the article [HRW98] by Herzog, Reiner and Welker, where this complex is shown to be homotopy equivalent to a wedge of spheres of dimension $|V| - 3$ and the number of spheres is the number of acyclic orientations of $G$ minus one. Jonsson [Jon05] showed the coloring complex to be constructible and hence Cohen-Macaulay. This result was improved by Hultman [Hul07] who showed the coloring complex to be shellable and by Hersh and Swartz [HS08] who showed that the coloring complex has a convex ear decomposition. These results translate into bounds on the coefficients of $\chi_G$.

In this article we concentrate on establishing the structural result that the four counting polynomials are Hilbert functions in Steingrímsson's sense. We deal with the question of obtaining bounds on the coefficients in the companion article [BD10]. In the present article, we only characterize the coefficient vectors of Hilbert polynomials of ideals of Steingrímsson's type in Section 7. In [BD10] we exploit geometric information to derive stronger constraints for these four polynomials.

# 4 Hilbert equals Ehrhart

In this section we relate Ehrhart functions of certain complexes to Hilbert functions of ideals defined in terms of these complexes. We begin with the well-known relation between simplicial complexes and the corresponding Stanley-Reisner ideals, move on to relative simplicial complexes and relative Stanley-Reisner ideals before we finally consider relative polytopal complexes. (i) As Ehrhart functions are defined in terms of geometric simplicial complexes while Stanley-Reisner ideals are defined in terms of abstract simplicial complexes, all the complexes we consider live in both worlds. A geometric simplicial complex $\Delta$ has an abstract simplicial complex $\text{comb}(\Delta)$ associated with it, see Section 2.

Let $\Delta$ be an abstract simplicial complex on the ground set $V$. We identify the elements of the ground set of $\Delta$ with the variables in the polynomial ring $\mathbb{K}[x_v : v \in V] := \mathbb{K}[x]$. Thus sets $S \subset V$ correspond to square-free monomials in $\mathbb{K}[x]$. The **Stanley-Reisner ideal** $I_\Delta$ of $\Delta$ is generated by the monomials corresponding to the minimal non-faces of $\Delta$, more precisely

$$I_{\Delta} := \langle x^{u} \in K[x] | \text{supp}(u) \notin \Delta \rangle.$$

Then, the **Stanley-Reisner ring** of $\Delta$ is the quotient $\mathbb{K}[\Delta] = \mathbb{K}[x]/I_\Delta$. We equip the ring $\mathbb{K}[x]$ with the standard grading, that is for any monomial $x^u \in \mathbb{K}[x]$ we have $\deg(x^u) = ||u||_1 = \sum_{i=1}^n u_i$. The fundamental result about Stanley-Reisner rings is this:

<footnote>(i) We introduce the polytopal Stanley-Reisner ideals corresponding to polytopal complexes only later in Section 6.</footnote>
**Theorem 2** [Sta96] Let $\Delta$ be a $d$-dimensional (abstract) simplicial complex with $f_i$ faces of dimension $i$ for $0 \le i \le d$. Then the Hilbert function $H_{\mathbb{K}[\Delta]}$ of the Stanley-Reisner ring $\mathbb{K}[\Delta]$ satisfies

$$ H_{\mathbb{K}[\Delta]}(k) = \sum_{i=0}^{d} f_i \binom{k-1}{i} \qquad (3) $$

for $k \in \mathbb{Z}_{>0}$ and $H_{\mathbb{K}[\Delta]}(0) = 1$.

We remark that the right-hand side of (3) evaluated at zero gives $\sum_{i=0}^{d} f_i \binom{-1}{i} = \chi(\Delta)$, the Euler characteristic of $\Delta$.

If we are given a geometric simplicial complex $\Delta$ we will generally use $\mathrm{vert}(\Delta)$ as the ground set of the abstract simplicial complex $\mathrm{comb}(\Delta)$ and identify the variables of $\mathbb{K}[x]$ with the vertices of $\Delta$. In this case we use $I_{\Delta}$ to refer to $I_{\mathrm{comb}(\Delta)}$ and similarly for $\mathbb{K}[\Delta]$.

Now the Ehrhart functions of a unimodular $d$-dimensional lattice simplex $\sigma^d$ and its relative interior relint $\sigma^d$ are, respectively,

$$ L_{\sigma^d}(k) = \binom{k+d}{d} \quad \text{and} \quad L_{\mathrm{relint}} \sigma^d(k) = \binom{k-1}{d}. \qquad (4) $$

Taken together, (3) and (4) tell us that for any (geometric) simplicial complex $\Delta$ in which all simplices are unimodular, the Ehrhart function $L_{\Delta}(k) = |\mathbb{Z}^d \cap k \cup \Delta|$ of $\Delta$ satisfies

$$ L_{\Delta}(k) = \sum_{\sigma \in \Delta} L_{\mathrm{relint}} \sigma(k) = \sum_{i=0}^{d} f_i \binom{k-1}{i} = H_{\mathbb{K}[\Delta]}(k) \qquad (5) $$

for all $k \in \mathbb{Z}_{>0}$. Simply put: the Ehrhart function of a unimodular geometric simplicial complex and the Hilbert function of the corresponding Stanley-Reisner ring coincide. This fact is well-known, see for example [MS05]. Taking the above approach and calculating the Ehrhart functions of open simplices, however, allows us to do without Möbius inversion.

For our purpose we need a more general concept than that of a Stanley-Reisner ring. For an abstract simplicial complex $\Delta$ the Hilbert function $H_{\mathbb{K}[\Delta]}(k)$ counts all those monomials $x^u$ of degree $k$ with $\mathrm{supp}(u) \in \Delta$. We are interested in a pair of simplicial complexes $\Delta' \subset \Delta$, the former being a subcomplex of the latter, and want to count those monomials $x^u$ such that $\mathrm{supp}(u) \notin \Delta'$ but $\mathrm{supp}(u) \in \Delta$. To that end we follow Stanley [Sta96] in calling a pair of simplicial complexes $\Delta' \subset \Delta$ a **relative simplicial complex**. We denote by $I_{\Delta/\Delta'}$ the ideal in $\mathbb{K}[\Delta]$ generated by all monomials $x^u$ with $\mathrm{supp}(u) \notin \Delta'$. We call this the **relative Stanley-Reisner ideal**. Its Hilbert function $H_{I_{\Delta/\Delta'}}(k)$ counts the number of non-zero monomials $x^u$ of degree $k$ in $I_{\Delta'} \setminus I_{\Delta}$ or, equivalently, the number of non-zero monomials $x^u$ in $\mathbb{K}[x]$ with $\mathrm{supp}(u) \in \Delta \setminus \Delta'$. (Notice how the roles of $\Delta$ and $\Delta'$ swap, depending on whether we formulate the condition using ideals or using complexes). Now, as Stanley remarks, Theorem 2 carries over to the relative case.

**Theorem 3** [Sta96] Let $\Delta' \subset \Delta$ be a relative $d$-dimensional abstract simplicial complex and let $f_i$ denote the number of $i$-dimensional simplices in $\Delta \setminus \Delta'$. Then for all $k \in \mathbb{Z}_{>0}$

$$ H_{I_{\Delta/\Delta'}}(k) = \sum_{i=0}^{d} f_i \binom{k-1}{i}. \qquad (6) $$
If $\Delta$ is a geometric simplicial complex and $\Delta' \subset \Delta$ a subcomplex, we also call the pair $\Delta' \subset \Delta$ a relative geometric simplicial complex and define its relative Stanley-Reisner ideal $I_{\Delta/\Delta'}$ to be $I_{\text{comb}(\Delta)/\text{comb}(\Delta')}$.

By the same argument as above, we conclude that for any relative $d$-dimensional geometric simplicial complex $\Delta' \subset \Delta$, all faces of which are unimodular,

$$L \cup \Delta \cup \Delta'(k) = \sum_{\sigma \in \Delta \setminus \Delta'} L_{\text{relint}}(\sigma)(k) = \sum_{i=0}^{d} f_i \binom{k-1}{i} = H_{I_{\Delta/\Delta'}(k)} \quad (7)$$

for all $k \in \mathbb{Z}_{>0}$, i.e. the Ehrhart function of a relative simplicial complex with unimodular faces and the Hilbert function of the associated relative Stanley-Reisner ideal coincide. Moreover this function is a polynomial in $k$ as

$$\binom{k-1}{i} = \frac{1}{i!} \prod_{i=1}^{i} (k-i)$$

is a polynomial for every $i \in \mathbb{Z}_{\ge 0}$ using the convention that $i! = \prod_{j=1}^{i} j$ and empty products are 1.

To be able to deal with the applications in Section 5 we need to go one step further. The complexes we will be dealing with, are not going to be simplicial. Their faces will be polytopes. So we define a **relative polytopal complex** to be a pair $C' \subset C$ of polytopal complexes, the former a subcomplex of the latter. Our goal is to realize the Ehrhart function $L \cup C \cup C'(k)$ as the Hilbert function of a relative Stanley-Reisner ideal.

By the above arguments, it would suffice to require that $C$ has a unimodular triangulation. But for the sake of convenience we would like to impose a condition on $C$ that can be checked one face at a time. Requiring that each face of $C$ has a unimodular triangulation would not be sufficient. A unimodular triangulation $\Delta_F$ for each face $F \in C$ does not guarantee that $\cup_{F \in C} \Delta_F$ is a unimodular triangulation of $C$: It may be that for faces $F_1, F_2 \in C$ that share a common face $F = F_1 \cap F_2$ the unimodular triangulations $\Delta_{F_1}$ and $\Delta_{F_2}$ do not agree on $F$, i.e.

$$\{F \cap f_1 | f_1 \in \Delta_{F_1}\} \neq \{F \cap f_2 | f_2 \in \Delta_{F_2}\}.$$

Fortunately there is the notion of a compressed polytope: it suffices to require of each face $F \in C$ individually that $F$ is compressed, to guarantee that $C$ as a whole has a unimodular triangulation.

Let $P \subset \mathbb{R}^d$ be a lattice polytope. Let $\prec$ be a total ordering of the lattice points in $P$. The **pulling triangulation** $\text{pull}(P; \prec)$ of $P$ with respect to the total ordering $\prec$ is defined recursively as follows. If $P$ is an empty simplex, then $\text{pull}(P; \prec)$ is the complex generated by $P$. Otherwise $\text{pull}(P; \prec)$ is the complex generated by the set of polytopes

$$\bigcup_F \{\text{conv}\{v, G\} : G \in \text{pull}(F; \prec)\}$$

where $v$ is the $\prec$-minimal lattice point in $P$ and the union runs over all faces $F$ of $P$ that do not contain $v$. See also Sturmfels [Stu96]. This construction yields a triangulation and the vertices of $\text{pull}(P; \prec)$ are lattice points in $P$. Pulling triangulations need not be unimodular, in fact the simplices in a pulling triangulation do not even have to be empty! Polytopes whose pulling triangulation is always unimodular get a special name. A polytope $P$ is **compressed** if for any total ordering $\prec$ on the vertex set the pulling triangulation $\text{pull}(P; \prec)$ is unimodular. These definitions have the following well-known properties.
**Proposition 4** 1. Any $\dim(P)$-dimensional simplex in $\mathrm{pull}(P, \prec)$ contains the $\prec$-minimal lattice point $v$ in $P$ as a vertex.

2. $\mathrm{pull}(F, \prec) = \mathrm{pull}(P, \prec) \cap F$ for any total order $\prec$ on the lattice points in $P$ and any face $F$ of $P$.

3. All faces of a compressed polytopes are compressed.

4. Compressed polytopes are empty.

A proof of this proposition can be found in [Bre09]. For more information on pulling triangulations and compressed polytopes we refer to [Stu96, OH01, Sul04, Stu91].

Now, if $C$ is a polytopal complex with integral vertices such that every face $P \in C$ is compressed, then we can fix an arbitrary total order $\prec$ on $\bigcup C \cap \mathbb{Z}^d$ and construct the pulling triangulations $\mathrm{pull}(P, \prec)$ of all faces $P \in C$ with respect to that one global order $\prec$. By Proposition 4 this means that the for any two $P_1, P_2 \in C$ that share a common face $F = P_1 \cap P_2$ the triangulations induced on $F$ agree: $\mathrm{pull}(P_1, \prec) \cap F = \mathrm{pull}(F, \prec) = \mathrm{pull}(P_2, \prec) \cap F$. Thus $\mathrm{pull}(C, \prec) := \bigcup_{F \in C} \mathrm{pull}(F, \prec)$ is a unimodular triangulation of $C$ with $\mathrm{vert}(C) = \mathrm{vert}(\mathrm{pull}(C, \prec))$. We abbreviate $\Delta := \mathrm{pull}(C, \prec)$.

If $C'$ is any subcomplex of $C$, we define $\Delta'$ to be the subcomplex of $\Delta$ consisting of those faces $F \in \Delta$ such that $F \subset \bigcup C'$. So

$$L \cup C \cup C'(k) = L \cup \Delta \cup \Delta'(k) = H_{I_{\Delta/\Delta'}}(k) \quad (8)$$

for $k \in \mathbb{Z}_{>0}$ which means that we have realized the Ehrhart function of $\bigcup C \setminus \bigcup C'$ as the Hilbert function of the relative Stanley-Reisner ideal $I_{\Delta/\Delta'}$. Moreover, we have already seen that this function is a polynomial. We summarize these results in the following theorem.

**Theorem 5** Let $C$ be a polytopal complex. If all faces of $C$ are compressed lattice polytopes, then for any subcomplex $C' \subset C$ there exists a relative Stanley-Reisner ideal $I_{\Delta, \Delta'}$ such that for all $k \in \mathbb{Z}_{>0}$

$$L \cup C \cup C'(k) = H_{I_{\Delta/\Delta'}}(k)$$

and this function is a polynomial.

# 5 Counting Polynomials as Hilbert Functions

In this section we apply Theorem 5 to obtain analogues of Steingrímsson's Theorem 1 for all five counting polynomials. A useful tool in this context is going to be the following theorem by Ohsugi and Hibi which states that lattice polytopes that are slices of the unit cube are automatically compressed.

**Theorem 6** (Ohsugi and Hibi [OH01]) Let $P$ be a lattice polytope in $\mathbb{R}^n$. If $P$ is lattice isomorphic to the intersection of an affine subspace with the unit cube, i.e. $P \approx [0, 1]^n \cap L$ for some affine subspace $L$, then $P$ is compressed. (ii)

<footnote>(ii) Actually, Ohsugi and Hibi showed a more general result, but this will suffice for our purposes. Interestingly, Sullivant [Sul04] noted that this condition is also necessary for a lattice polytope to be compressed.</footnote>
## Integral Flow and Tension Polynomials

Let $S$ be the linear subspace of $\mathbb{R}^E$ given by (2). The $k$-flows of $G$ are in bijection with the lattice points in $k \cdot (-1, 1)^E \cap S$. Furthermore let $\mathcal{H} = \{\{x|x_e = 0\} | e \in E\}$ denote the arrangement of all coordinate hyperplanes. Then the nowhere zero $k$-flows of $G$ are in bijection with the lattice points in $k \cdot (-1, 1)^E \cap S \setminus \bigcup \mathcal{H}$. The closures of the components of $(-1, 1)^E \cap S \setminus \bigcup \mathcal{H}$ are of the form $(\prod_{e \in E}[a_e, a_e + 1]) \cap S$ for some $a \in \{-1, 0\}^E$. Let $\mathcal{C}$ be the polytopal complex generated by these and let $\mathcal{C}'$ be the subcomplex of all faces of $\mathcal{C}$ contained in the boundary of $[-1, 1]^E$ or contained in one of the coordinate hyperplanes. Then $\varphi_G(k) = L \cup C \cup C'(k)$. Because (2) gives rise to a totally unimodular matrix, the maximal faces of $\mathcal{C}$ are lattice polytopes. (iii) Moreover by Theorem 6, they are compressed. Thus Theorem 5 can be applied to yield the following result.

**Theorem 7** For any graph $G$ there exists a relative Stanley-Reisner ideal $I_{\Delta/\Delta'}$ such that for all $k \in \mathbb{Z}_{>0}$

$$ \varphi_G(k) = H_{I_{\Delta/\Delta'}}(k). $$

The above geometric construction can be found in [BZ06b]. A similar construction given in [Dal08] can be used to show an analogue of the above theorem for the integral tension polynomial.

**Theorem 8** For any graph $G$ there exists a relative Stanley-Reisner ideal $I_{\Delta/\Delta'}$ such that for all $k \in \mathbb{Z}_{>0}$

$$ \theta_G(k) = H_{I_{\Delta/\Delta'}}(k). $$

## Modular Flow and Tension Polynomials

Let $v \in V$ and define the vector $a^v \in \{0, \pm 1\}^E$ by $a_e^v = +1$ if $\mathrm{head}(e) = v \neq \mathrm{tail}(e)$, $a_e^v = -1$ if $\mathrm{head}(e) = v = \mathrm{tail}(e)$, and $a_e^v = 0$ otherwise. Let $A$ denote the matrix with the vectors $a^v$ for $v \in V$ as rows. Now, we identify the integers $\{0, \dots, k-1\}$ with their respective cosets in $\mathbb{Z}_k$ so that a function $f: E \to \mathbb{Z}_k$ can be viewed as an integer vector $f \in [0, k]^E$. Using this identification all equations (2) hold for a given $f$ if and only if $Af = kb$ for some $b \in \mathbb{Z}^V$. Thus the set of nowhere zero $\mathbb{Z}_k$-flows on $G$ can be identified with the set of lattice points in $k \cdot ((0, 1)^E \cap \bigcup_b H_b)$ where $H_b = \{f | Af = b\}$ and $b$ ranges over all integer vectors such that $(0, 1)^E \cap H_b \neq \emptyset$. Let $\mathcal{C}$ be the complex generated by the respective closed polytopes $[0, 1]^E \cap H_b$. Let $\mathcal{C}'$ be the subcomplex consisting of all those faces that are contained in the boundary of the cube $[0, 1]^E$. Then $\bar{\varphi}_G(k) = L \cup C \cup C'(k)$. The faces of $\mathcal{C}$ are lattice polytopes because $A$ is totally unimodular and by Theorem 6, they are compressed. Thus Theorem 5 can be applied to yield the following result.

**Theorem 9** For any graph $G$ there exists a relative Stanley-Reisner ideal $I_{\Delta/\Delta'}$ such that for all $k \in \mathbb{Z}_{>0}$

$$ \bar{\varphi}_G(k) = H_{I_{\Delta/\Delta'}}(k). $$

The above geometric construction can be found in [BS09], which also contains a similar construction using which an analogue of the above theorem for the modular tension polynomial can be shown [Bre09].

**Theorem 10** For any graph $G$ there exists a relative Stanley-Reisner ideal $I_{\Delta/\Delta'}$ such that for all $k \in \mathbb{Z}_{>0}$

$$ \bar{\theta}_G(k) = H_{I_{\Delta/\Delta'}}(k). $$

<footnote>(iii) We refer to [Sch86] for the concept of a totally unimodular matrix and related results.</footnote>
## Chromatic Polynomial

Let $G$ be a graph without loops. (iv) For each $e \in E$ define $H_e = \{x | x_{\text{head}(e)} = x_{\text{tail}(e)}\}$ and consider the graphic hyperplane arrangement $\mathcal{H} = \{H_e | e \in E\}$. Then the proper $k$-colorings of $G$ are in bijection with the lattice points in $k \cdot ([0, 1)^E \setminus \bigcup \mathcal{H})$. The closure of any component $C$ of $[0, 1)^E \setminus \bigcup \mathcal{H}$ is of the form $P_\sigma = \{x \in [0, 1]^V | \sigma_e(x_{\text{head}(e)} - x_{\text{tail}(e)}) \ge 0\}$ where $\sigma \in \{\pm 1\}^E$ is a sign vector. Let $\mathcal{C}$ be the polytopal complex generated by the $P_\sigma$ and let $\mathcal{C}'$ be the subcomplex consisting of all faces that are contained in some hyperplane $H_e$ or in some hyperplane of the form $\{x | x_v = 1\}$ for some $v \in V$. Then $\chi_G(k) = L \cup C \cup C'(k)$. The faces of $\mathcal{C}$ are lattice polytopes and it can be shown that they are compressed. Thus Theorem 5 can be applied to yield the following result.

**Theorem 11** For any graph $G$ there exists a relative Stanley-Reisner ideal $I_{\Delta/\Delta'}$ such that for all $k \in \mathbb{Z}_{>0}$

$$ \chi_G(k) = H_{I_{\Delta/\Delta'}}(k). $$

This is an improvement upon Steingrímsson's Theorem insofar as we obtain the chromatic polynomial $\chi_G(k)$ itself as a Hilbert function of a relative Stanley-Reisner ideal and not the shifted polynomial $\chi_G(k+1)$. To obtain the shifted chromatic polynomial using the above construction we would need to consider the closed cube $[0, 1]^V$ instead of the half-open cube $[0, 1)^V$. A geometric construction similar to the one given above can be found in [BZ06a].

# 6 Non-Square-Free Ideals

What if the relative polytopal complex $\mathcal{C}$ does not have a unimodular triangulation? It turns out that if the polytopes in $\mathcal{C}$ are normal lattice polytopes, the Ehrhart function of $\bigcup \mathcal{C} \setminus \bigcup \mathcal{C}'$ is still the Hilbert function of an ideal $I_2$ in a ring $\mathbb{K}[x]/I_1$, however we cannot guarantee that the ideals $I_1, I_2$ are square-free. That is, we are dealing with a relative multicomplex instead of a relative simplicial complex.

A lattice polytope $P$ is **normal** if for every $k \in \mathbb{N}$ every $z \in kP \cap \mathbb{Z}^d$ can be written as the sum of $k$ points in $P \cap \mathbb{Z}^d$. Note that a compressed polytope is automatically normal.

With this notion we can generalize Theorem 5 to include another case where the polytopal complex in question satisfies a weaker condition. The conclusion we obtain in this case is not as strong, however.

**Theorem 12** Let $\mathcal{C}$ be a polytopal complex in which all faces are normal lattice polytopes. Then for any subcomplex $\mathcal{C}' \subset \mathcal{C}$ there exist a monomial ideal $I_1$ in a polynomial ring $\mathbb{K}[x]$ equipped with the standard grading and a monomial ideal $I_2$ in $\mathbb{K}[x]/I_1$ such that for all $k \in \mathbb{Z}_{>0}$

$$ L \cup C \cup C'(k) = H_{I_2}(k) $$

and this function is a polynomial. If the faces of $\mathcal{C}$ are compressed, then moreover the ideals $I_1$ and $I_2$ can be chosen to be square-free.

The case where the faces of $\mathcal{C}$ are compressed and the ideals are square-free is just Theorem 5. We are not going to prove this again. Instead we give a self-contained algebraic proof of the case where the faces are only normal and we do not conclude that the ideals are square-free.

<footnote>(iv) If $G$ contains loops, then $\chi_G(k) = 0$ which, trivially, is a Hilbert function.</footnote>
First we define the **polytopal Stanley-Reisner ideal** $I_C$ of the polytopal complex $C$ by

$$I_C := \langle x^a | \text{ there is no } P \in C \text{ such that } \text{supp}(a) \subset P \rangle$$

where again $\text{supp}(a)$ denotes the set of lattice points $u$ such that $a_u \neq 0$.

**Proof:** By homogenization, that is by passing to the complex generated by $\{P \times \{1\} | P \in C\}$, we can assume without loss of generality that for every lattice point $z$ there is at most one integer $k$ such that $z \in k \cup C$.

We are going to construct ideals $I_2 \supset I_1$ in a polynomial ring $\mathbb{K}[x]$ such that the monomials in $I_2 \setminus I_1$ of degree $k$ are in bijection with the lattice points in $k(\bigcup C \setminus \bigcup C')$.

Now consider the polynomial ring $\mathbb{K}[x_u : u \in \bigcup C \cap \mathbb{Z}^d]$ equipped with the standard grading. Let $\prec$ be a term order on this polynomial ring. Let $U$ be the matrix that has the vectors $u$ as columns. Let $n$ be the number of columns of $U$ and let $d$ be the number of rows. We define

$$I_1 := I_C + \langle x^b | x^b \notin I_C \text{ and there is an } x^a \notin I_C \text{ such that } Ua = Ub \text{ and } x^a \prec x^b \rangle,$$

$$I_2 := I_{C'}$$

where $I_C$ and $I_{C'}$ denote the polytopal Stanley-Reisner ideals of the complexes $C$ and $C'$ respectively. We call a monomial $x^a$ valid if $x^a \notin I_1$ but $x^a \in I_2$. Now we claim that the map $\pi : x^a \mapsto Ua$ defines a bijection between the valid monomials of degree $k$ and the lattice points in $k(\bigcup C \setminus \bigcup C')$.

If $x^a$ is valid and of degree $k$, then $Ua \in k(\bigcup C \setminus \bigcup C') \cap \mathbb{Z}^d$. First, we notice that $Ua \in \mathbb{Z}^d$, because $a$ and $U$ are integral. Second, we argue that $Ua \in k \cup C$. Because $x^a$ is valid, there exists a polytope $P$ such that $\text{supp}(a) \subset P$ and thus $Ua \subset kP$. Finally, we show that $Ua \notin k \cup C'$. Suppose $Ua \in kP'$ for an inclusion-minimal $P' \in C'$. Because $C'$ is a subcomplex of $C$, this implies that $P'$ is a face of $P$ and $\text{supp}(a) \subset P'$. Hence $x^a \notin I_{C'}$, which is a contradiction to $x^a$ being valid.

$\pi$ is surjective. Let $v \in k(\bigcup C \setminus \bigcup C') \cap \mathbb{Z}^d$ for some $k$. Then there is a polytope $P \in C \setminus C'$ such that $v \in \text{relint}(kP)$. By the assumption that $P$ is normal, there exists a non-negative integral representation $b$ of $v$ in terms of lattice points in $P \cap \mathbb{Z}^d$: $v = \sum_{u \in P \cap \mathbb{Z}^d} b_u u = Ub$. So by construction $x^b \notin I_C$ and $Ub = v$. Consider the $\prec$-minimal monomial $x^a \notin I_C$ with $Ua = Ub$. For this monomial we have $x^a \notin I_1$. Moreover, as $Ua = v \in \text{relint}(kP)$ we have $x^a \in I_2$. Finally we have to check that $\text{deg}(x^a) = k$. All elements of $\text{supp}(a)$ are lattice points in $P$, so $Ua \in \text{deg}(x^a)P$. However by our assumption at the beginning there is at most one integer $k'$ such that $v = Ua \in k'P$. Thus $\text{deg}(x^a) = k$.

$\hat{\pi}$ is injective. By definition of $I_1$ and as $\prec$ is a total order on the set of monomials, for every $v \in k(\bigcup C) \cap \mathbb{Z}^d$ there is at most one monomial $x^a \notin I_1$ such that $Ua = v$. $\square$

We remark that this approach can also be used to give another proof of Theorem 5 using a fundamental correspondence between compressed polytopes and lattice point sets such that the corresponding toric ideal has square-free initial ideals under any reverse-lexicographic term order (see [Stu96]). This approach is explored in [Dal08] and [Bre09]. [Bre09] also contains a variant of the above result, due to Breuer and Sanyal, in the case where $\mathbb{K}[x]$ is equipped with a non-standard grading.

# 7 Bounds on the Coefficients

($k-1$) is a polynomial of degree $d$ in $k$. The polynomials ($k-1$) for $0 \le i \le d$ form a basis of the $\mathbb{K}$-vector space of all polynomials in $\mathbb{K}[k]$ of degree at most $d$ and the polynomials ($k-1$) for $0 \le i$ form a basis of
$\mathbb{K}[k]$ when seen as a $\mathbb{K}$-vector space. By Theorem 3 the coefficients of the Hilbert function of a relative Stanley-Reisner ideal expressed with respect to this basis must be non-negative and integral. It turns out that this characterizes which polynomials appear as Hilbert functions of relative Stanley-Reisner ideals.

**Theorem 13** A polynomial $f(k) = \sum_{i=0}^{d} f_i \binom{k-1}{i}$ is the Hilbert function of some relative Stanley-Reisner ideal $I_{\Delta/\Delta'}$ if and only if $f_i \in \mathbb{Z}_{\ge 0}$ for all $0 \le i \le d$.

**Proof:** We have already seen that the coefficients of $H_{I_{\Delta/\Delta'}}(k)$ with respect to the basis $\binom{k-1}{d}$, $d \in \mathbb{Z}_{\ge 0}$ are necessarily non-negative integers. To see that this is also sufficient, let $f(k) = \sum_{i=0}^{d} f_i \binom{k-1}{i}$ with $f_i \in \mathbb{Z}_{\ge 0}$ for all $0 \le i \le d$. For $0 \le i \le d$ and $1 \le j \le f_i$ let $\sigma_j^i$ denote a closed unimodular lattice simplex of dimension $i$ in $\mathbb{R}^d$ such that the $\sigma_j^i$ are pairwise disjoint. Let $\Delta$ denote the (disjoint) union of all these $\sigma_j^i$ and define $\Delta'$ to be the union of the respective boundaries $\partial\sigma_j^i$. Then the set $\bigcup \Delta \setminus \bigcup \Delta'$ is the disjoint union of $f_d$ relatively open unimodular lattice simplices of dimension $d$, $f_{d-1}$ relatively open unimodular lattice simplices of dimension $d-1$ and so on. Consequently $H_{I_{\Delta/\Delta'}}(k) = L \cup \Delta \setminus \Delta'(k) = f(k)$ as desired. $\square$

This immediately implies that all the counting functions we considered have non-negative integral coefficients with respect to this basis.

**Theorem 14** The modular and integral flow and tension polynomials as well as the chromatic polynomial of a graph have non-negative integer coefficients with respect to the basis $\{\binom{k-1}{d} | 0 \le d \in \mathbb{Z}\}$ of $\mathbb{K}[k]$.

For the modular and integral flow polynomials and the integral tension polynomial this is a new result, whereas for the chromatic polynomial and thus for the modular tension polynomial this is implicit in the previous work on the coloring complex. However, these bounds are not very strong, as we have not used any of the geometric information particular to these polynomials.

In [BD10] we give stronger constraints on the coefficients of the modular and integral flow and tension polynomials. There, we do not build on the realization of these polynomials as Hilbert functions, we rather make direct use of our geometric realization of these polynomials as Ehrhart functions of inside-out polytopes. We show that a wide class of inside-out polytopes, including those arising in these constructions, have a convex ear decomposition and use this fact to derive bounds.

## Acknowledgements

We thank Matthias Beck and Christian Haase for suggesting this topic to us and for pointing us to the notion of compressed polytopes.

## References

[BD10] Felix Breuer and Aaron Dall. Bounds on the coefficients of tension and flow polynomials. arxiv:math/1004.3470v1, 2010.

[BR07] Matthias Beck and Sinai Robins. *Computing the continuous discretely*. Undergraduate Texts in Mathematics. Springer, New York, 2007.

[Bre09] Felix Breuer. *Ham Sandwiches, Staircases and Counting Polynomials*. PhD thesis, Freie Universität Berlin, 2009.
[BS09] Felix Breuer and Raman Sanyal. Ehrhart theory, modular flow reciprocity, and the Tutte polynomial. arXiv:math/0907.0845v1, 2009.

[BZ06a] Matthias Beck and Thomas Zaslavsky. Inside-out polytopes. *Adv. Math.*, 205(1):134–162, 2006.

[BZ06b] Matthias Beck and Thomas Zaslavsky. The number of nowhere-zero flows on graphs and signed graphs. *J. Combin. Theory Ser. B*, 96(6):901–918, 2006.

[Dal08] Aaron Dall. The flow and tension complexes. Master's thesis, San Francisco State University, 2008.

[HRW98] Jürgen Herzog, Vic Reiner, and Volkmar Welker. The Koszul property in affine semigroup rings. *Pacific Journal of Mathematics*, 186(1):39–65, 1998.

[HS08] Patricia Hersh and Ed Swartz. Coloring complexes and arrangements. *Journal of Algebraic Combinatorics*, 27(2):205–214, 2008.

[Hul07] A Hultman. Link complexes of subspace arrangements. *European Journal of Combinatorics*, 28(3):781–790, 2007.

[Jon05] Jakob Jonsson. The topology of the coloring complex. *Journal of Algebraic Combinatorics*, 21:311–329, 2005.

[Koc02] Martin Kochol. Polynomials associated with nowhere-zero flows. *J. Combin. Theory Ser. B*, 84(2):260–269, 2002.

[MS05] Ezra Miller and Bernd Sturmfels. *Combinatorial Commutative Algebra*, volume 227 of *Graduate Texts in Mathematics*. Springer-Verlag, 2005.

[OH01] Hidefumi Ohsugi and Takayuki Hibi. Convex polytopes all of whose reverse lexicographic initial ideals are squarefree. *Proceedings of the American Mathematical Society*, 129(9):2541–2546, 2001.

[Sch86] Alexander Schrijver. *Theory of linear and integer programming*. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons Ltd., Chichester, 1986. A Wiley-Interscience Publication.

[Sta96] Richard P. Stanley. *Combinatorics and Commutative Algebra Second Edition*, volume 41 of *Progress in Mathematics*. Birkhäuser, 1996.

[Ste01] Einar Steingrímsson. The coloring ideal and coloring complex of a graph. *Journal of Algebraic Combinatorics*, 14:73–84, 2001.

[Stu91] Bernd Sturmfels. Gröbner bases of toric varieties. *Tôhoku Math. Journal*, 43:249–261, 1991.

[Stu96] Bernd Sturmfels. *Gröbner Bases and Convex Polytopes*, volume 8 of *University Lecture Series*. American Mathematical Society, 1996.

[Sul04] Seth Sullivant. Compressed polytopes and statistical disclosure limitation. arXiv:math/0412535v1, 2004.