Bounds on the coefficients of tension and flow polynomials

DOI 10.1007/s10801-010-0254-4

Bounds on the coefficients of tension and flow polynomials

Felix Breuer·Aaron Dall

Received: 30 April 2010 / Accepted: 1 September 2010 / Published online: 23 September 2010

© Springer Science+Business Media, LLC 2010

Abstract The goal of this article is to obtain bounds on the coefficients of modu- lar and integral flow and tension polynomials of graphs. To this end we use the fact that these polynomials can be realized as Ehrhart polynomials of inside-out poly- topes. Inside-out polytopes come with an associated relative polytopal complex and, for a wide class of inside-out polytopes, we show that this complex has a convex ear decomposition. This leads to the desired bounds on the coefficients of these polyno- mials.

Keywords Ehrhart polynomial·Inside-out polytope·Convex ear decomposition· Regular subdivision·Polytopal complex·M-vector

1 Introduction

The goal of this article is to obtain bounds on the coefficients of modular and inte- gral flow and tension polynomials of graphs. To this end we employ Ehrhart theory, the theory of lattice points in polyhedra. In past research [2,3,5,7,12] it has been shown that each of these polynomials can be realized as the Ehrhart polynomial of inside-out polytopes. Inside-out polytopes come with an associated relative polytopal complexC⊆C. In this article we show that for a wide class of inside-out polytopes, this polytopal complex can be triangulated so that the resulting relative simplicial complex⊆is unimodular and admits a convex ear decomposition (Theo- rem2). This implies constraints on the Ehrhart polynomial of the inside-out polytope

F. Breuer (

Freie Universität Berlin, Arnimallee 3, 14195 Berlin, Germany e-mail:[email protected]

A. Dall

Universitat Politècnica de Catalunya, Jordi Girona 1-3, 08034 Barcelona, Spain e-mail:[email protected]

(Theorem4). In the case of modular flow and tension polynomials, which is of greater interest in graph theory than the integral case, this leads to upper and lower bounds on the coefficients of these polynomials (Theorem5). In the integral case, Theorem4 calls for a closer analysis of the Ehrhart polynomials of flow and tension polytopes, which we begin in Sect.8. In particular we obtain upper and lower bounds on the h^∗-vector of tension and flow polytopes.

This article is related to similar work done for the chromatic polynomial of a graph. Steingrímsson [26] showed that the chromatic polynomial of graph can be realized as the Hilbert function of a certain square-free monomial ideal, which in turn gave rise to what Steingrímsson called the coloring complex of a graph. Subsequent articles, building on Steingrímsson’s work, have investigated various properties of the coloring complex. Jonsson [18] showed the coloring complex to be constructible and hence Cohen–Macaulay. This result was improved by Hultman [17] who showed the coloring complex to be shellable and by Hersh and Swartz [15] who showed that the coloring complex has a convex ear decomposition. These results translate into bounds on the coefficients of the chromatic polynomial.

Breuer and Dall [6] have shown that the integral and modular flow and tension polynomials of a graph can also be realized as Hilbert functions of square-free mono- mial ideals, working with the theory of lattice polytopes rather than the theory of Stanley-Reisner rings. In the present article we continue this work to obtain bounds on the coefficients of these polynomials. As we only need to focus on the geometry to obtain our results, we do not use that these are Hilbert functions but only that they are Ehrhart polynomials.

This article is organized as follows. We begin in the realm of discrete geometry where we use Sect.2to give some preliminary definitions. We then focus on regular subdivisions of polytopes in Sect.3where we show that the subdivision determined by an inside-out polytope is regular (Lemma2). We introduce the four counting poly- nomials in Sect.4and summarize the realization of these as Ehrhart polynomials of inside-out polytopes. In Sect.5we define convex ear decompositions and show that regular triangulations of the complexes associated with inside-out polytopes have a convex ear decomposition. As we need to relate theh-vector of an abstract simpli- cial complex to the Ehrharth^∗-vector of a relative polytopal complex, we give an overview of the well-known relationships betweenf-,h- andh^∗-vectors in Sect.6.

We are then in the position to derive our main results in Sect.7. To deal with the inte- gral case, more work has to be done, which we begin in Sect.8by obtaining bounds on theh^∗-vectors of flow and tension polytopes.

2 Preliminaries from discrete geometry

Before we begin, we gather some definitions from discrete geometry. We recommend the textbooks [1,30] as references.

The Ehrhart functionL_A of any setA⊆Rⁿ is defined byL_A(k)= |Zⁿ∩k·A| for k∈N. A lattice polytope is a polytope in Rⁿ such that all vertices are integer points. It is a theorem of Ehrhart that the Ehrhart functionL_P(k)of a lattice polytope is a polynomial ink. Two polytopes P , Qare lattice isomorphic, P ≈Q, if there

exists an affine isomorphismAsuch thatA|_Zⁿ is a bijection ontoZⁿ andAP =Q.

Ad-simplex is the convex hull ofd+1 affinely independent points. Ad-simplex is unimodular if it is lattice isomorphic to the convex hull ofd +1 standard unit vectors. A hyperplane arrangement is a finite collectionHof affine hyperplanes and Hdenotes the union of all of these. A cell ofHis the closure of a component of the complement of

H. We use the notation H_a,b=

x∈Rⁿ| a, x =b fora∈Rⁿandb∈Rto denote hyperplanes.

A polytopal complex is a finite collectionCof polytopes in someRⁿwith the fol- lowing two properties: IfP ∈CandF is a face ofP, thenF∈C; and ifP , Q∈Cthen P∩Q∈Cis common face of bothP andQ. The polytopes inCare called faces and C, the union of all faces ofC, is called the support ofC. A (geometric) simplicial complex is a polytopal complex in which all faces are simplices. An abstract simpli- cial complex is a setof subsets of a finite setV such thatis closed under taking subsets. A geometric simplicial complex gives rise to an abstract simplicial complex and every abstract simplicial complex can be realized by a geometric one. We will not distinguish notationally between these two notions as it will be clear from the context which is meant. A polytopal complexCthat is a subsetC⊆Cof a polytopal complexC is called a subcomplex ofC. Subcomplexes of abstract simplicial com- plexes are defined similarly. Given a collectionSof polytopes inRⁿsuch that for any P , Q∈Sthe setP ∩Qis a face of bothP andQ, the polytopal complexCgener- ated byS, isC= {F|Fa face ofP∈S}. A subdivision of a polytopal complexCis a polytopal complexCsuch that

C=

Cand every face ofCis contained in a face ofC. A triangulation is a subdivision in which all faces are simplices. A unimodular triangulation is a triangulation in which all simplices are unimodular.

A relative polytopal complexC⊆Cis a pair of polytopal complexesCandCsuch thatCis a subcomplex ofC. An inside-out polytope is a pair(P ,H)of a polytope P ⊆Rⁿ and a finite collection of hyperplanes HinRⁿ such that each hyperplane H ∈H meets the relative interior ofP. Every inside-out polytope (P ,H) comes with an associated relative polytopal complexC⊆C, where C is generated by the cells of the hyperplane arrangement intersected withP andCis the subcomplex of C consisting of all those faces ofC that are contained in

H∪∂P. The Ehrhart functionL_{(P ,H)}of an inside-out polytope is the Ehrhart function of

C\ C, i.e., L_{(P ,H)}(k)=

Zⁿ∩k·

intP \ H

for k∈N. We call an inside-out polytope integral if all the faces of C are lattice polytopes. In this caseL_{(P ,H)}(k)is a polynomial ink.

3 Regular subdivisions

We are going to use the concept of a regular subdivision of a polytope. For a thorough treatment of this concept we refer to [8,20,27]. In this section we show that the poly- topal complexes induced by inside-out polytopes are regular subdivisions. Moreover

we present two tools from the literature that we are going to use. This will enable us to show in Sect.5that the complexes that interest us have convex ear decompositions.

Loosely speaking, a polytopal complexP is a regular subdivision of ad-polytope P if it is a subdivision ofP and there exists a(d+1)-polytopeQsuch thatP is the projection of the lower hull ofQ. More precisely, we letP be ad-polytope and assume without loss of generality thatP ⊆R^d× {0} ⊆R^d+1and defineπ to be the map(v₁, . . . , v_d, v_d+1)→(v₁, . . . , v_d,0)that forgets the last coordinate. A polytopal complexPwith

P=P is a regular subdivision ofP ⊆Rⁿif there exists a(d+1)- polytopeQ⊆R^d+1 such that the facets of P are precisely the images underπ of those facets ofQwhose outer normalu=(u1, . . . , ud+1)hasud+1<0. A regular triangulation is a regular subdivision that is a triangulation.

We note that having a regular subdivision is hereditary in the sense that ifC is a subcomplex ofPsuch that

Cis a polytope andP is a regular subdivision of P, thenCis a regular subdivision of

C.

If we can show that a given simplicial complex is a regular triangulation, this tells us that we can realize this complex as a subcomplex of the boundary of a simplicial polytope.

Lemma 1 LetP be ad-polytope andP a regular triangulation ofP. Then:

(a) P|∂P is combinatorially equivalent to the boundary complex of a simpliciald- polytope.

(b) P is combinatorially equivalent to a subcomplex of the boundary complex of a simplicial(d+1)-polytope.

Proof (a) is a result by Bruns and Römer [9, Lemma 9]. To show (b) we observe that by assumptionP is combinatorially equivalent to the lower hull of some(d+1)- polytopeQ. LetQ be a polytope obtained by perturbing the vertices ofQslightly.

ThenQ is simplicial andP is combinatorially equivalent to a subcomplex of the

boundary ofQ, as desired.

To give a formal proof of the fact that a given complex is indeed a regular sub- division, it is convenient to work with a different definition of regular subdivision, that is easily seen to be equivalent: LetCbe a polytopal complex whose support is a polytopeP. A functionω:P →Ris aC-linear strictlyC-convex support function if the following properties hold.

(a) ωis continuous.

(b) ωis affine on eachF∈C.

(c) ωis convex onP.

(d) The convex setsS⊆P that are inclusion maximal with the property that there exists an affine functionf such thatf ≤ωandf|S=ω|S, are exactly the facets ofC.

We call a convex setSwith the properties given in (d) a domain of linearity. A sub- divisionCofP possesses aC-linear strictlyC-convex support function if and only if Cis a regular subdivision ofP.

Lemma 2 Let (P ,H) be an inside-out polytope and letC⊆C be the associated relative polytopal complex. ThenCis a regular subdivision ofP.

Proof For every affine hyperplaneH∈Hwe define a functionω_H:P →Ras fol- lows. Letzbe any point inH, letvbe a normal vector ofHand define

ωH(x):=v, z − v, x .

As can be checked easily,ω_H is continuous and affine on each of the two half-spaces defined byH. Moreoverω_H is convex, i.e.,

ωH λx+(1−λ)y

≤λωH(x)+(1−λ)ωH(y), (1) where the inequality above is strict if and only ifx, y /∈Hlie in opposite half-spaces.

Now, we define a functionω:P →Rby ω(x)=

H∈H

ωH(x).

We claim that this function is aC-linear strictlyC-convex support function.

(a) ωis continuous because it is a sum of continuous functions.

(b) ωis affine on eachF∈C, because each of theω_His affine onF. (c) ωis convex because it is a sum of convex functions.

All that we have left to show is property (d).

LetS⊆P be a convex set that is inclusion maximal with respect to the property that there is an affine functionf :

C→Rwithf ≤ωandf|S=ω|S. Assume that there existx, y∈Sthat are contained in the relative interior of two different maximal faces ofC. That means that there is a hyperplaneH₀∈Hthat separates the two. Then we have

f 1

2x+1 2y

=ω 1

2x+1 2y

<1

2ω(x)+1

2ω(y)=1

2f (x)+1 2f (y) because inequality (1) holds strictly forω_H0 and weakly for all otherω_H. But this means thatf is not affine onS, a contradiction. We conclude that no two points in Scan be separated by a hyperplane inH, which shows thatSmust be contained in a maximal faceF ∈C.

To show thatFis contained inSconsider the following. We already know thatω|F

is an affine function. BecauseF is full-dimensional,ω|F can be extended uniquely to an affine functionf :P →Rand we havef|F =ω|F by construction. Letx∈P be any point. Pick a pointy=x that lies in the relative interior ofF and choose λ∈(0,1) such that λx+(1−λ)y also lies in the relative interior of F. This is possible becauseP is convex andF is full-dimensional. Then

λf (x)+(1−λ)f (y)=f λx+(1−λ)y

=ω λx+(1−λ)y

≤λω(x)+(1−λ)ω(y).

Becausef (y)=ω(y) this impliesf (x)≤ω(x). Thusf demonstrates thatF is a domain of linearity. As S was defined to be inclusion maximal, we can conclude F=S.

We have now shown that every such setSis a maximal face ofC. But the above argument also shows that any maximal faceF ∈Cis a domain of linearity. Therefore

the proof is complete.

Of courseCis not going to be simplicial in general. To obtain a simplicial complex, we need to refineCfurther. To this end we use the concept of a pulling refinement, see [27]: Given a polytopal complexC and a vertexv of Cwe define the complex pull(C, v), obtained by pullingv, by

pull(C, v)= {F ∈C|v /∈F} ∪

Q

{conv(F∪v)|F a face ofQ, v /∈F},

where the union runs over allQ∈C such thatv∈Q. A pulling refinement ofCis a polytopal complex obtained by pulling several vertices ofCin a given order. A pulling triangulation ofCis a pulling refinement ofCthat is a triangulation. One important property of this method of refinement is that pulling a vertex preserves regularity of the subdivision: IfCis a regular subdivision of a polytopeP andC is a pulling refinement ofC, thenCis a regular subdivision ofP. See [14,20].

A lattice polytopeP such that all pulling triangulations ofP are unimodular is called compressed. An integral inside-out polytopeP with associated relative poly- topal complexC⊆Cis compressed if all faces ofCare compressed.

4 Flow and tension polynomials as Ehrhart functions

Both the modular and integral variants of the flow and tension polynomials of a graph can be represented as Ehrhart functions of inside-out polytopes. In this section we de- fine these polynomials and summarize the constructions of the corresponding inside- out polytopes. For the general graph-theoretic background we refer the reader to [29].

A detailed treatment of the material in this section can be found in [5, Chaps. 3–4].

Throughout this paper, let G be a graph with edge set E and vertex set V. In general G may have multiple edges and/or loops. However, when studying flows (resp. tensions), we exclude graphs that have bridges (resp. loops), as there are no nowhere-zero flows (tensions) in these cases. We now fix an orientation ofG, which we use to define flows and tensions. It is important to note, however, that all counting polynomials studied in this article are invariants of the underlying undirected graph and are independent of the chosen orientation.

A spanning forestT ofGis a maximal cycle-free spanning subgraph ofG. With any pathP in the underlying undirected graph we can associate a sign vectorσ∈ {0,±1}^E by lettingσe= +1 ife∈P and the orientation ofeand the direction of traversal ofeare the same, by lettingσe= −1 ife∈P and the orientation ofeand the direction of traversal ofeare opposite, and by lettingσ_e=0 ife /∈P.

LetAbe the vertex-edge incidence matrix of G. We will interpretA as both a matrix with entries in Z and as a matrix with entries in Zk. In the former case,

kerA⊆R^E is the flow space ofG and vectorsf ∈kerA∩ {−k+1, . . . , k−1}^E are called k-flows ofG. In the latter case, vectorsf ∈kerA⊆Z^E_k are called Zk- flows. We will identify integers with their respective cosets inZk and cosets inZk

with their canonical representatives inZ. Thus we may view the set ofk-flows as be- ing contained in the open cube(−k, k)^E and the set ofZk-flows as being contained in the half-open cube[0, k)^E.

LetMdenote the cycle-edge incidence matrix, i.e., the matrix whose row vectors are the sign vectors of all cycles ofG. Again we interpretMas both a matrix with entries inZand as a matrix with entries inZk. In the former case, kerM⊆R^Eis the tension space ofGand vectorst∈kerM∩{−k+1, . . . , k−1}^Eare calledk-tensions ofG. In the latter case, vectorst∈kerA⊆Z^E_k are calledZk-tensions. Again we may view the set ofk-tensions as being contained in the open cube(−k, k)^E and the set ofZk-tensions as being contained in the half-open cube[0, k)^E.

We call a vectorz, with entries inZor inZk, nowhere-zero ifz_e=0 for alle∈E.

Now we define for allk∈N

ϕG(k)=#{nowhere-zerok-flows ofG}

¯

ϕ_G(k)=#{nowhere-zeroZk-flows ofG} θ_G(k)=#{nowhere-zerok-tensions ofG} θ¯_G(k)=#{nowhere-zeroZk-tensions ofG}.

It turns out that all of these functions are polynomials ink. The polynomialsϕ¯Gand θ¯_G are called the modular flow and tension polynomials ofG, respectively. These are the classic graph polynomials defined by Tutte. They are evaluations of the Tutte polynomial and can be computed recursively, using a deletion-contraction formula.

The modular tension polynomial,θ¯_G, is a non-trivial divisor of the chromatic poly- nomial ofG.ϕ_Gandθ_G are called the integral flow and tension polynomials ofG, respectively. That these are in fact polynomials is a relatively recent result by Kochol [19]. They were studied more intensively in [11] and [12].

From the above definitions it is straightforward to see that the integral flow and tension polynomials of a graph are Ehrhart functions of inside-out polytopes. See [5,6] for details. LetHdenote the hyperplane arrangement consisting of all coordi- nate hyperplanesH_ei,0. Then

ϕG(k)=L_{kerA∩(−1,1)}E,H(k) and θG(k)=L_{kerM∩(−1,1)}E,H(k).

These constructions are from [2,3,12]. The inside-out polytopes kerA∩(−1,1)^E,H

and kerM∩(−1,1)^E,H

are integral (which follows from the total unimodularity ofAandM, see [22]) and compressed (which follows e.g. from a theorem by Ohsugi and Hibi [21, Theo- rem 1.1]).

To obtain the modular flow and tension polynomials as Ehrhart functions of inside- out polytopes, we have a bit more work to do. LetT be a spanning forest ofG. To every non-tree edgee∈E\T with tail(e)=u and head(e)=v there corresponds

a unique pathP inT fromv tou. Letσ^e denote the sign vector of this path. Let C denote the|T| × |E\T|-matrix that has the vectorsσ^e|T as columns. Any flow f onG is uniquely determined byf|E\T via f|T =Cf|E\T. Any tensiont onG is uniquely determined byt|T viat|E\T =(−C^t)t|T. We can therefore parameterize nowhere-zeroZk-flows (Zk-tensions) by lattice points in the open unit cube(0, k)^E\T (resp.(0, k)^T), subject to certain constraints that can be expressed via the matrixC.

LetA denote the set of rows of C and let B denote the set of rows of −C^t. Let H_Adenote the set of hyperplanesH_a,k wherea∈Aandk∈Zsuch thatH_a,kmeets int(0,1)^E\T. LetH_Bdenote the set of hyperplanesH_b,kwhereb∈Bandk∈Zsuch thatHb,kmeets int(0,1)^T. Then

¯

ϕ_G(k)=L_(0,1)E\T,HA(k) and θ¯_G(k)=L_(0,1)T,HB(k).

The inside-out polytopes((0,1)^E\T,H_A)and((0,1)^T,H_B)are integral (which fol- lows from the total unimodularity ofC, see [22]) and compressed (which follows, e.g., from Paco’s Lemma, see [14, Proposition 1.8]). The above constructions were given by Breuer and Sanyal in [5, 7], to which we refer the interested reader for details. See also [6].

For any spanning forestT, the matrixC defined above can also be used to con- struct inside-out polytopes in the integral case. For a graphGwith a fixed spanning forestT we define the tension polytopeT_Gby

T_G=

t∈R^T | −1≤C^tt≤1,−1≤t≤1 and the flow polytopeF_Gby

FG=

f∈R^E\T | −1≤ −Cf ≤1,−1≤f ≤1 ,

where 1 denotes the all-ones vector and the inequalities hold componentwise. Let HT denote the collection of hyperplanes inR^T given byC^tt=0 together with the coordinate hyperplanes. Then the inside-out polytope(T_G,HT)is a lattice transform of the inside-out polytope given above for the integral tension case and in partic- ular L_(TG,HT) =θG. Let HF denote the collection of hyperplanes in R^E\T given byCf =0 together with the coordinate hyperplanes. Then the inside-out polytope (F_G,HF)is a lattice transform of the inside-out polytope given above for the in- tegral flow case and in particular L_(FG,HF)=ϕ_G. In [13], the authors prove that (certain unimodular transformations of) generalized tension polytopes give rise to all distributive polytopes and give a connection to alcoved polytopes.

We summarize the content of this section in the following theorem.

Theorem 1 For every graphG, the modular and integral flow and tension polyno- mials ofGcan be realized as Ehrhart polynomials of compressed, integral inside-out polytopes.

5 Convex ear decompositions

Definition 1 Let be a (d −1)-dimensional simplicial complex. A convex ear decomposition of is an ordered sequence 1, 2, . . . , m of pure (d −1)- dimensional subcomplexes ofsuch that

(a) 1is the boundary complex of ad-polytope. For eachj≥2,_jis a(d−1)-ball that is a proper subcomplex of the boundary complex of a simpliciald-polytope.

(b) ∂_j=_j∩

i<j_i forj ≥2.

(c) =

j_j.

Convex ear decompositions are of interest because the existence of a convex ear decomposition of a compleximplies bounds on theh-vector of, see Theorem3 below. To be able to apply this result, we now establish that inside-out polytopes have convex ear decompositions in the following sense.

Theorem 2 Let(P ,H)be an inside-out polytope and let⊆be a regular trian- gulation of the associated relative polytopal complex. Then bothand|∂P have a convex ear decomposition.

Proof We show only thathas a convex ear decomposition. The proof that|∂P

has a convex ear decomposition is analogous.

LetC⊆C denote the relative polytopal complex associated with the inside-out polytope(P ,H). By Lemma2,C is a regular subdivision ofP. By assumption is a regular triangulation ofC. By transitivityis a regular triangulation ofP. By Lemma1(a) the complex|∂P is combinatorially equivalent to the boundary com- plex of a simpliciald-polytope, whered=dimP. So we can define the first element in our convex ear decomposition to be₀:=|∂P.

Next we fix a total orderH₁, . . . , H_lof the hyperplanes inH. For any hyperplane H, we denote the positive and negative closed half-spaces byH⁺andH⁻, respec- tively. Now for any 1≤j ≤land any functionσ: {1, . . . , j−1} → {+,−}we define the setP_j^σ to be the intersection

P_j^σ:=P∩

1≤k<j

H_k^{σ (k)}.

Note thatP_j^σ is either empty ord-dimensional as the hyperplanes all meet the interior ofP. Next we define

C_j^σ:=P_j^σ ∩H_j and ^σ_j :=|C_j^σ.

For a givenj, we denote the set of allσ such that^σ_j is(d−1)-dimensional byS_j and we equipS_j with an arbitrary total order≺.

The complete set of ears for our convex ear decomposition is {₀} ∪

^σ_j|1≤j≤l, σ∈S_j .

The total order≺ we impose on this set is defined as follows. ₀ is its minimal element. Moreover^σ_j¹

1 ≺^σ_j²

2, ifj₁< j₂or ifj₁=j₂andσ₁≺σ₂. Now we have to show that this really gives a convex ear decomposition.

(a) We note that for everyjandσ, the complex^σ_j is a regular triangulation of the (d−1)-dimensional polytopeC_j^σ. (C|C^σ_j is a regular subdivision ofC^σ_j and|C^σ_j

is a regular triangulation ofC|C^σ_j.) Thus it is a pure(d−1)-dimensional simplicial complex which is a(d−1)-dimensional ball and by Lemma1(b) it is combinatori- ally equivalent to a proper subcomplex of the boundary of a simpliciald-polytope.

Moreover it is a subcomplex of. (b) Next we observe that for everyj

0∪

1≤k<j

σ∈S_k

^σ_j =∂P ∪

1≤k<j

(Hk∩P )

which is a superset of∂^σ_j for every σ ∈S_j. On the other hand, no interior point of^σ_j is contained in∂P or any of the hyperplanesH_k withk < j. Moreover, no interior point of^σ_j is contained in any^σ_j forσ=σ. Thus

∂^σ_j =^σ_j ∩

0∪

k<j σ∈Sk

^σ_k ∪

σ≺σ

^σ_j

.

(c) Finally we note that on the level of sets

0∪

1≤j≤l

σ∈Sj

^σ_j =∂P ∪

1≤j≤l

H_j∩P=

and thus the same holds on the level of complexes as, ₀ and the ^σ_j are all subcomplexes of. This shows that the above is a convex ear decomposition of.

6 Thef-,h- andh^∗-vectors of polynomials

Let p(k) be a polynomial in k of degree d. We define the h^∗-vector h^∗(p)= (h^∗₀, . . . , h^∗_d)ofpby

p(k)= d

i=0

h^∗_i

k+d−i d

.

Here we use the fact that the polynomials ^k+_d^d−i

for 0≤i≤d form a basis of the vector space of polynomials of degree at mostd. Equivalently, theh^∗-vector can be defined by the equation

(1−z)^d+1

p(0)+

k≥1

p(k)z^k

= d

i=0

h^∗_izⁱ.

Similarly, we define theh-vectorh(p)=(h₀, . . . , h_d+1)ofpby p(k)=

k+d d

+

d+1

i=1

hi

k+d−i d

andh0=1. Here we use the fact that the polynomials ^k+_d^d−i

for 1≤i≤d+1 form a basis of the vector space of polynomials of degree at mostd. Note that theh-vector has lengthd+1 while theh^∗-vector has only lengthd. This is due to the fact that the first entry of theh-vector is always 1, while the first entry of theh^∗-vector isp(0).

Equivalently, theh-vector can be defined by the equation (1−z)^d+1

1+

k≥1

p(k)z^k

=

d+1

i=0

hizⁱ.

Finally, we define thef-vectorf (p)=(f0, . . . , f_d)ofpby p(k)=

d

i=0

f_i k−1

i

.

Here we use the fact that the polynomials ^k−_i¹

, 0≤i≤dform a basis of the vector space of polynomials of degree at mostd.

Then theh-vector and theh^∗-vector of a given polynomial are related by h^∗_i =hi+(−1)^d+i

d+1 i

hd+1 (2)

for 0≤i≤d subject to the constraint thath0=1. Similarly, thef- and theh-vector are related by

h_i=(−1)ⁱ d+1

i

+

i−1

k=0

(−1)^i−k−1

d−k i−k−1

f_k (3)

for 0≤i≤d+1.

Of course we are mainly interested in the case wherepis the Ehrhart polynomial of some polytopal complex. LetCbe ad-dimensional polytopal complex such that all vertices ofCare lattice points. LetL_Cdenote the Ehrhart polynomial ofC. Then we defineh^∗(C):=h^∗(L_C). When applying the above definition of anh^∗-vector in this case, it is important to note thatL_C(0)denotes the value of the Ehrhart polynomial at zero and not the value of the lattice point enumerator at zero, see also [24, p. 255]. If Cis a polytope, thenh^∗(C)is the classicalh^∗-vector or Ehrhart-δ-vector of a lattice polytope.

For ad-dimensional simplicial complex, thef-vectorf ()=(f₀, . . . , f_d)is classically defined by lettingfi equal the number ofi-dimensional simplices in. Theh-vectorh() is then defined by the relation (3). See [4,25,30]. Note that in this case the Euler characteristicχ ()ofis

χ ()=1+(−1)^dh_d+1(). (4)

Moreover, ifis unimodular, thenL(0)=h^∗₀()=χ (), see Lemma3below.

To our knowledgef- andh-vectors of polynomials have previously not been ex- plicitly defined. Our choice of terminology is justified by the following well-known fact.

Lemma 3 Letbe a unimodular triangulation of an integral polytopal complexC.

(a) f ()=f (L_C).

(b) h()=h(L_C).

(c) IfCis a topological ball, thenh^∗()=h().

Proof (a) follows directly from the fact that the Ehrhart polynomial of the relative interior of a unimodulari-simplex is ^k−_i¹

. (b) follows from (a) by the relation be- tween thef- andh-vectors. For shellable complexes, see [30], this can also be seen directly by noting that the Ehrhart polynomial of a unimodulard-simplex that hasi faces removed is ^k+d−i_d

. (c) follows from 1=χ ()=h^∗₀()by (2) and (4).

Notice that for a lattice polytope P, the constant term of L_P is 1 and hence h(L_P)=h^∗(L_P).

Lemma 4 Letpandq be polynomials with deg(p)=deg(q)=d. (a) If deg(p+q)=d, thenh^∗(p+q)=h^∗(p)+h^∗(q).

(b) If deg(p+q)=d−1, thenh^∗_i(p+q)=_i

j=0h^∗_j(p)+h^∗_j(q)for 0≤i≤d−1.

Proof (a) is immediate from the definition. (b) can be seen by observing that _d−1

j=0h^∗_j(p+q)z^j (1−z)^d =

_d

j=0h^∗_j(p)z^j (1−z)^d+1 +

_d

j=0h^∗_j(q)z^j (1−z)^d+1 , which implies

d−1

j=0

h^∗_j(p+q)z^j=

i≥0

zⁱ

· d

j=0

h^∗_j(p)z^j+ d

j=0

h^∗_j(q)z^j

from which the claim follows by comparing coefficients.

It turns out that theh^∗-vectors of the polynomialsk^dand(2k+1)^d are given by Eulerian and MacMahon numbers, respectively. Givenn∈Nand 0≤i≤nwe define the Eulerian numberA(n, i)and the MacMahon numberB(n, i)by

A(n, i)= i

j=0

(−1)^j n+1

j

(i−j )ⁿ

B(n, i)= i

j=1

(−1)^i−j n

i−j

(2j−1)ⁿ⁻¹.

These are sequences A008292 and A060187 in the Online Encyclopedia of Integer Sequences [23] with the exception that we also considerA(n,0)=B(n,0)=0. If we letA(n, n+1)=0, then we have for 0≤i≤n

h^∗_i kⁿ

=A(n, i), (5)

h^∗_i (k+1)ⁿ

=A(n, i+1), (6)

h^∗_i (2k+1)ⁿ

=B(n+1, i+1). (7) All of these identities are straightforward to compute, see also [1, Sect. 2.2].

7 Enumerative consequences

For positive integershandithere exists a unique sequence of integersa_i > a_i−1>

· · ·> a_j≥j≥1 such that

h= a_i

i

+ a_i−1

i−1

+ · · · + a_j

j

.

We then define

hⁱ :=

a_i+1 i+1

+

a_i−1+1 i

+ · · · +

a_j+1 j+1

.

Now, a sequence of non-negative integers(h0, . . . , hd)is anM-vector ifh0=1 and hi+1≤h_iⁱ for all 1≤i≤d−1. We say that a vectorh=(h0, . . . , hd)of d+1 integers satisfies theg-constraints if

(a) h₀≤h₁≤ · · · ≤h_d/2. (b) h_i≤h_d−i fori≤d/2.

(c) (h₀, h₁−h₀, h₂−h₁, . . . , h_d/2−h_d/2−1)is anM-vector.

Theorem 3 (Chari, Swartz) Letdenote an abstract(d−1)-dimensional simplical complex with a convex ear decomposition. Then theh-vector of satisfies theg- constraints.

This is [15, Theorem 14], where the first two constraints are due to Chari [10] and the last constraint is due to Swartz [28].

Combining this result with our Theorem2yields the following result about Ehrhart polynomials of inside-out polytopes.

Theorem 4 Let (P ,H) be an integral inside-out polytope in which all faces are compressed. Then theh-vector of the polynomial L_P(k)−L_{(P ,H)}(k) satisfies the g-constraints.

Proof Let ⊆ be any pulling triangulation of the relative polytopal complex C⊆Cassociated with(P ,H). By Lemma2,C is a regular subdivision and, as

arises fromC by pulling vertices,is a regular triangulation ofP. By Theorem2 we conclude thathas a convex ear decomposition. So, by Theorem3, theh-vector ofsatisfies theg-constraints. All faces of(P ,H)are compressed, so all faces of are unimodular. Thus, by Lemma3, theh-vectors ofandL coincide and we conclude that

h L_P(k)−L_{(P ,H)}(k)

=h L(k)

=h()

satisfies theg-constraints as desired.

This implies bounds on the coefficients of modular flow and tension polynomials of graphs, by virtue of the fact that in these casesP is a unit cube and thusL_P(k)= (k+1)^d.

Theorem 5 Letpdenote the modular flow polynomial or the modular tension poly- nomial of a graph. Letddenote the degree ofp. Then theh-vector of the polynomial (k+1)^d−p(k)satisfies theg-constraints.

Proof As we have seen in Sect.4, the modular flow or tension polynomial of any graph can be realized as the Ehrhart polynomial of an integral inside-out polytope (P ,H)with compressed faces, whereP = [0,1]^d andd denotes the degree of the polynomial. The claim now follows from Theorem4and the fact thatL_[0,1]d(k)=

(k+1)^d.

8 The integral case

In the case of the integral flow and tension polynomials, the inside-out polytopes (P ,H)are not of the formP= [0,1]^d. Rather,P will depend on the graph, so, given a polynomialp, we cannot compute a polynomialp such that ifp is a, say, flow polynomial thenpsatisfies theg-constraints. The best we can say is the following.

Theorem 6 Letpdenote the integral flow polynomial or the integral tension poly- nomial of a graphG. ThenL_FG(k)−p(k)orL_TG(k)−p(k), respectively, satisfy the g-constraints.

Proof As we have seen in Sect. 4, the integral flow or tension polynomial of any graph can be realized as the Ehrhart polynomial of an integral compressed inside- out polytope(F_G,H)or(T_G,H), respectively. The claim then follows from Theo-

rem4.

To check whether a givenpsatisfies this necessary condition, say in the flow case, we would have to check whetherL_FG(k)−p(k) satisfies theg-constraints for all graphsGwithϕ_G=p. So the question arises which polynomials are of the form L_FG orL_TG for some graphG: Which polynomials are Ehrhart polynomials of in- tegral flow or tension polytopes? We address this question in this section by giving constraints on theh^∗-vectors of these polynomials.

First we exploit some nice geometric properties of integral flow and tension poly- topes to show that theirh^∗-vectors are palindromic.

Definition 2 A lattice polytopeP is reflexive if (a) intP∩Z^d= {0}.

(b) int((k+1)P )∩Z^d=kP∩Z^dfor allk∈Z>0.

The following proposition gives a method for obtaining new reflexive polytopes from a given reflexive polytope.

Proposition 1 LetP be a reflexived-polytope and letSbe a linear subspace ofR^d. IfQ:=P ∩Sis a lattice polytope, thenQis reflexive.

Proof SinceS a subspace,Q^◦∩Z^d= {0}. Suppose x∈Z^d∩(k+1)Q^◦\kQfor somek∈Z>0, thenx is also in(k+1)P^◦\kP. This contradicts the fact that P is

reflexive.

TakingP = [−1,1]^m (where m= |E|) and lettingS be the flow space (tension space, respectively) in Proposition1yields

Corollary 1 Integral flow and tension polytopes of a finite graphGare reflexive.

The following theorem, due to Hibi, gives a beautiful connection between the geometry of reflexive polytopes on the one hand and palindromich^∗-vectors on the other.

Theorem 7 (Hibi [16]) LetP be a latticed-polytope with the origin in its interior.

P is reflexive if and only if the vectorh^∗(P )is palindromic, i.e., it satisfiesh^∗_i =h^∗_d−i for 0≤i≤ ^d₂.

Combining Corollary1and Theorem7yields

Theorem 8 LetGbe any finite graph. Thenh^∗(F_G)andh^∗(T_G)are palindromic.

Our next goal is to produce vectorsfl, fu, tl,andtusuch that theh^∗-vector of any flow polytope (respectively, tension polytope) satisfiesf_l≤h^∗≤f_u(resp.t_l≤h^∗≤ t_u). To this end we use Stanley’s Monotonicity Theorem (for polytopes):

Theorem 9 (Stanley [24]) LetP ⊆Qbe latticed-polytopes. Thenh^∗(P )≤h^∗(Q).

To apply this result we use the variants of flow and tension polytopes from Sect.4 that were defined with respect to a fixed spanning forest.

Lemma 5 LetG=(V , E_G)be a finite graph withccomponents. Then any tension polytopeT_GofGis a subpolytope of[−1,1]^|V|−c. LetH=(V , E_H)be a subgraph ofGwith the same number of components. ThenTG⊆TH for a suitable choice of spanning forest.

Proof By the construction given in Sect.4,T_G⊆ [−1,1]^|V|−c.

By assumption there is a spanning forestF of H that is also a spanning forest ofG. Let the tension polytopesT_G andT_H both be constructed with respect toF. AsE_G\F ⊇E_H\F, the set of inequalities definingT_Gis a superset of the set of

inequalities definingT_H. ThusT_G⊆T_H.

We can now give upper and lower bounds onL_TG.

Theorem 10 LetGbe a connected finite graph withnvertices. Then theh^∗-vector of the tension polytopeT_Gsatisfies

A(n, i+1)=h^∗_i (k+1)ⁿ−kⁿ

≤h_i(TG)≤h^∗_i (2k+1)ⁿ⁻¹

=B(n, i+1) for 0≤i≤n−1 and these bounds are tight for alln.

Note that ifGhasccomponentsG1, . . . , G_c, thenL_TG=_c

i=1L_TGi.

Proof By Lemma5we know thatT_G⊆ [−1,1]ⁿ⁻¹ and by Theorem9 and (7) we conclude thath^∗_i(T_G)≤h_i(L_[−1,1]n−1)=B(n, i+1)for all 0≤i≤n−1. This bound is realized as[−1,1]ⁿ⁻¹, which is the tension polytope of any tree onnvertices.

By Theorem5, we have that, for any spanning forest ofG,TK_n ⊆TG. Thus to obtain the lower bound we must show thath^∗(LT_Kn)=A(n, i+1).

First we show thatLT_Kn =(k+1)ⁿ−kⁿ. To see this note thatLT_Kn counts the number of(k+1)-tensions onKn. The(k+1)-tensions ofKnare in bijection with the functionscin the set

C=

c:V →Z|c(v_i)−c(v_j)≤k,min

v∈Vc(v)=0 .

Because we are dealing with the complete graph the functionsc∈Ctake only values in{0, . . . , k}and for functionsc:V → {0,1, . . . , k}the condition|c(v_i)−c(v_j)| ≤k is automatically satisfied. So we can writeCas

C=

c:V → {0,1, . . . , k} |min

v∈Vc(v)=0

=

c:V → {0,1, . . . , k}

\

c:V → {1, . . . , k} , and thus

LT_Kn(k)= |C| =(k+1)ⁿ−kⁿ.

Combining Lemma4with (5) and (6) yieldsh^∗_i((k+1)ⁿ−kⁿ)=A(n, i+1)for all

0≤i≤n−1.

We now turn our attention to integral flow polytopes. IfGis a planar graph andG is its dual, then, by the (vector space) duality of the flow and tension spaces, the flow polytope ofGis the tension polytope ofG. In this case, we can apply the theorem above to obtain bounds on the flow polynomial ofG.

In the non-planar case we proceed as follows. Let♦d denote thed-dimensional cross-polytope defined by

♦d=

xi∈R^{d d}

i=1

|x_i| ≤1

.

Lemma 6 LetG=(V , E)be a finite graph withc components and letr= |E| −

|V| +c. Then for any flow polytopeF_G ofGwe have that♦r ⊆F_G⊆ [−1,1]^r for any choice of spanning forest.

Proof By the construction given in Sect.4,F_G⊆ [−1,1]^r. Moreover, for any stan- dard unit vectore_iwe have thatCe_iis a{0,±1}-vector. Thuse_iand−e_iare contained

inF_G.

As in the case of tensions, this implies upper and lower bounds onh^∗(LF_G).

Theorem 11 LetG=(V , E)be a finite graph withccomponents and letr= |E| −

|V| +c. Then theh^∗-vector of the flow polytopeF_Gsatisfies r

i

≤h_i(F_G)≤h^∗_i (2k+1)^r

=B(r+1, i+1)

for 0≤i≤n−1. The upper bound is tight for allr.

Proof By Lemma6, ther-dimensional cross-polytope,♦r, is a subpolytope ofF_G. So by Stanley’s monotonicity theorem we have h^∗(L_♦r)≤h^∗(L_FG). The lower bound in the theorem stems from the well-known fact thath_i(L_♦r)= ^r_i

, see [1, Theorem 2.7]. Sinceh_i(L_[−1,1]^r)=h^∗_i((2k+1)^r)=B(r+1, i+1)by (7), the upper bound follows from Lemma6as well.

The upper bound in the above theorem is tight since, for any r∈N, the flow polytope of the graph consisting of a single vertex andrloops is[−1,1]^r. The lower bound, on the other hand, is not tight. For example, no 3-dimensional flow polytope

is lattice isomorphic to♦3.

Acknowledgements The authors would like to thank Christian Haase for bringing our attention to [9]

and two anonymous referees for their helpful comments. Felix Breuer was supported by Emmy Noether grant HA 4383/1 of the German Research Foundation (DFG).

References

1. Beck, M., Robins, S.: Computing the Continuous Discretely. Undergraduate Texts in Mathematics.

Springer, New York (2007)

2. Beck, M., Zaslavsky, T.: Inside-out polytopes. Adv. Math. 205(1), 134–162 (2006)

3. Beck, M., Zaslavsky, T.: The number of nowhere-zero flows on graphs and signed graphs. J. Comb.

Theory Ser. B 96(6), 901–918 (2006)

4. Billera, L.J., Björner, A.: Face Numbers of Polytopes and Complexes, 2nd edn., pp. 407–430. Chap- man & Hall/CRC Press, London/Boca Raton (2004). Chap. 18