# Ehrhart Positivity for Generalized Permutohedra

Federico Castillo, Fu Liu

► To cite this version:

Federico Castillo, Fu Liu. Ehrhart Positivity for Generalized Permutohedra. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.865-876, 10.46298/dmtcs.2505 . hal-01337767

HAL Id: hal-01337767

https://hal.science/hal-01337767

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Ehrhart Positivity for Generalized Permutohedra

Federico Castillo<fnref n="1" /> and Fu Liu <fnref n="1" /> †

**Abstract.** There are few general results about the coefficients of Ehrhart polynomials. We present a conjecture about their positivity for a certain family of polytopes known as generalized permutohedra. We have verified the conjecture for small dimensions combining perturbation methods with a new valuation on the algebra of rational pointed polyhedral cones constructed by Berline and Vergne.

**Résumé.** Il existe peu de résultats sur les coefficients des polynômes d'Ehrhart. On présente une conjecture concernant leur positivité pour une certaine famille de polytopes connus sous le nom de permutohèdre généralisé. On a vérifié la conjecture pour les petites dimensions en combinant des méthodes de perturbation avec une nouvelle valuation sur l'algèbre des cônes polyédraux rationnels pointés, construite par Berline et Vergne.

**Keywords:** Ehrhart polynomials, Generalized permutohedra, Perturbations, Valuations

## 1 Introduction

Let $P \subset \mathbb{R}^n$ be a lattice polytope. A natural enumerative problem is to compute $|P \cap \mathbb{Z}^n|$, the number of integral points contained in $P$. To study this question, it is very helpful to consider a more general counting problem. Define

$$L_P(n) := |nP \cap \mathbb{Z}^n|$$

It is a classic result that $L_P(n)$ is a polynomial in $n$. More precisely:

**Theorem 1.1 (Ehrhart)** There exists a polynomial $E_P(x)$ such that $E_P(n) = L_P(n)$ for any $n \in \mathbb{Z}_{\ge 0}$. Moreover, the degree of $E_P(x)$ is equal to the dimension of $P$.

We call $L_P(n)$ the *Ehrhart polynomial* of $P$. Some coefficients of $L_P(n)$ are well understood: the leading coefficient is equal to the normalized volume of $P$, the second coefficient is one half of the sum of the normalized volumes of facets, and the constant term is always 1. However, little is known about the other coefficients. They are not integers nor positive in general. We say a polytope has *Ehrhart positivity* or is *Ehrhart positive* if it has positive Ehrhart coefficients.

<footnote n="1">¹University of California, Davis, CA, USA.</footnote>

<footnote>†Fu Liu is partially supported by NSF grant DMS-1265702.</footnote>
There are few families of polytopes known to be Ehrhart positive. Zonotopes, in particular the regular permutohedra, are Ehrhart positive (Theorem 2.2 [14]). Cyclic polytopes also have this property. Their Ehrhart coefficients are given by the volumes of certain projections of the original polytope [5]. Stanley-Pitman polytopes are defined in [15] where a formula for the Ehrhart polynomial is given and from which Ehrhart positivity follows. Recently in [4] De Loera, Haws, and Koepp study the case of matroid polytopes and conjecture they are Ehrhart positive. Both Stanley-Pitman polytopes and matroid polytopes fit into a bigger family: generalized permutohedra.

In [11] Postnikov defines generalized permutohedra as polytopes obtained by moving the vertices of a usual permutohedron while keeping the same edge directions. That's what he called a generalized permutohedron of type $z$. He also considers a strictly smaller family, type $y$, consisting of sums of dilated simplices. He describes the Ehrhart polynomial for the type $y$ family in [11, Theorem 11.3], from which Ehrhart positivity follows. The type $y$ family includes the Stanley-Pitman polytopes, associahedra, cyclohedra, and more, but fails to contain matroid polytopes, which are type $z$ generalized permutohedra [1, Proposition 2.4].

We give the following conjecture:

**Conjecture 1.2** Generalized permutohedra are Ehrhart positive.

Note that since generalized permutohedra contain the family of matroid polytopes, our conjecture is a generalization of the conjecture on Ehrhart positivity of matroid polytopes given in [4] by De Loera et al.

The main result of this paper is to reduce the above conjecture to another conjecture which only concerns regular permutohedron, a smaller family of polytopes. Before we give the other conjecture, we need to introduce a result of Berline and Vergne. In [3], Berline and Vergne show that for any integral polytope $P$ the following exterior formula holds:

$$|P \cap \Lambda| = \sum_{F: \text{ a face of } P} \mathrm{vol}(F)\alpha(F, P) \quad (1)$$

where the volume is normalized and $\alpha(F, P)$ is a rational number which only depends on the tangent cone of $F$ at $P$. One immediate consequence of this formula is that if $\alpha(F, P)$ is positive for each face $F$ of $P$, then Ehrhart positivity follows. (See Theorem 3.8 and Lemma 3.9.) At present, the explicit computation of $\alpha(F, P)$ is a recursive, complicated process, but we carry it out in the special example of regular permutohedra of small dimensions, whose symmetry simplifies the computations. Based on our empirical results, we conjecture the following:

**Conjecture 1.3** For any face $F$ of the regular permutohedron $\Pi_n$, we have $\alpha(F, \Pi_n) > 0$.

Then our main theorem is that the Ehrhart positivity of all generalized permutohedra follows from the positivity of all the $\alpha$'s arising from the regular permutohedra.

**Theorem 1.4** Conjecture 1.3 implies conjecture 1.2.

The approach we will take to prove Theorem 1.4 is to use perturbation techniques, as in [6], to show that every generalized permutohedron can be slightly perturbed (in the sense of Definition 4.1) to get a *generic* generalized permutohedron (see Remark 2.10). More importantly, we show that these $\alpha$ values simply accumulate through perturbation; that is, each $\alpha$ for a generalized permutohedron is the sum of several $\alpha$'s for the regular permutohedron.

Since $\Pi_n$ is a much smaller family of polytopes than generalized permutohedra, and has a lot of symmetry, we are able to carry out direct computation to find values of $\alpha(F, \Pi_n)$. (See Section 5 for some
details.) We've verified that all $\alpha(F, \Pi_n)$ are positive for $n$ up to 7. (Note that the dimension of $\Pi_n$ is $n-1$.) Hence, the following result follows from Theorem 1.4.

**Theorem 1.5** All the generalized permutohedra of dimension at most 6 are Ehrhart positive. Hence, all the matroid polytopes of dimension at most 6 are Ehrhart positive.

Finally, in order to obtain the desired perturbation, we use a precise description of generalized permutohedra.

**Definition 1.6** Define the supermodular cone $C_n$ to be the set of all vectors $z \in V_n$, the vector space with basis indexed by subsets of $[n]$, such that

$$z_I + z_J \le z_{I \cap J} + z_{I \cup J}$$

for all $I, J$, intersected with $z_0 = 0$. This cone is $2^n - 1$ dimensional.

**Theorem 1.7** The polytope

$$P_z = \left\{ \mathbf{x} \in \mathbb{R}^n : \sum_{i=1}^{n} x_i = z_{[n]}, \sum_{i \in I} x_i \ge z_I, \forall I \subset [n] \right\}$$

is a generalized permutohedron if and only if $z \in C_n$

The above theorem is known. It was stated in [8] without proof and has been used implicitly since then. For example in [1], it is used to prove that matroid polytopes are indeed generalized permutohedra. Since it gives a very conceptual way to prove our important Proposition 4.4, and since we haven't found a proof in the literature, we include it here.

## 2 Generalized Permutohedra

**Definition 2.1** A polyhedron $P$ is the set of solutions of a system of inequalities

$$Ax \ge b$$

in $\mathbb{R}^n$ for some $m \times n$ matrix $A$ and $b \in \mathbb{R}^m$. A polytope is a bounded polyhedron.

We will be studying a family of polytopes with a very special inequality description. First we present one of them as a convex hull of a finite number of points.

**Definition 2.2** Given a point $(x_1, x_2, \dots, x_n) \in \mathbb{R}^n$, we construct the usual permutohedron

$$P(x_1, x_2, \dots, x_n) := \text{conv}((x_{\omega(1)}, x_{\omega(2)}, \dots, x_{\omega(n)}) : \omega \in S_n)$$

For all tuples of distinct $x_1, x_2, \dots, x_n$, the usual permutohedra will be similar in a sense that we now make precise.

**Definition 2.3** Given a polytope $P \subseteq \mathbb{R}^n$ and any face $F \subseteq P$ we define its normal cone as

$$N_P(F) := \{w \in \mathbb{R}^n : \langle w, a \rangle \ge \langle w, b \rangle \quad a \in F, b \in P\}$$

and the normal fan $N(P)$ is the collection of all normal cones over all its faces.
**Definition 2.4** The Braid Arrangement is the complete fan in $\mathbb{R}^n/(1, 1, \dots, 1)$ given by the hyperplanes

$$x_i - x_j = 0 \quad \text{for all } i \neq j.$$

As long as $x_1, x_2, \dots, x_n$ are distinct numbers, the resulting permutohedron have the braid arrangement as its normal fan. We focus on $\Pi_n := P(1, 2, \dots, n)$, called the regular permutohedron. Its inequality description is given by the following theorem [12].

**Theorem 2.5** The inequality description of the regular permutohedron is given by:

$$\Pi_n = \left\{ \mathbf{t} \in \mathbb{R}^n : \sum_{i \in [n]} t_i = \frac{n(n+1)}{2}, \sum_{i \in S} t_i \ge \binom{|S|+1}{2} \quad \forall S \subseteq [n], S \ne \emptyset, [n] \right\}$$

Moreover, all those $2^n - 2$ inequalities define the facets.

For the rest of the paper we use the following notation:

**Definition 2.6** Let $M_n$ be the $2^n \times n$ matrix in which each row corresponds to the indicator vector of all subsets of $[n]$. Let $V_n$ be the vector space with basis indexed by subsets of $[n]$.

With these definitions we can rewrite the previous theorem as

$$\Pi_n = \{ \mathbf{x} \in \mathbb{R}^n : M_n \mathbf{x} \ge \mathbf{b} \}$$

where $b \in V_n$ given by $b_S = \binom{|S|+1}{2}$, but for the rows $[n]$ and $\emptyset$ we have equality.

Now we come to the definition of the family of polytopes we study in this paper. We use the following definition which is equivalent to the original definition stated in [11] by a simple transformation on $S_n$:

**Definition 2.7** A generalized permutohedron is a polytope obtained from a usual permutohedron $P(x_1, \dots, x_n)$ by moving the vertices while keeping the direction of all the edges.

In other words, a generalized permutohedron is the convex hull of $n!$ points $v_\omega \in \mathbb{R}^n$ labeled by permutations $\omega \in S_n$ such that, for any $\omega \in S_n$ and any adjacent transposition $s_i = (i, i+1)$, we have,

$$v_{\omega} - v_{\omega s_i} = k_{\omega, i}(e_{\omega(i+1)} - e_{\omega(i)}), \quad (2)$$

for some nonnegative number $k_{\omega, i} \in \mathbb{R}_{\ge 0}$, where $e_1, \dots, e_n$ are the coordinate vectors in $\mathbb{R}$.

In [10], Postnikov, Reiner, and Williams give some equivalent definitions, among them the following:

**Proposition 2.8** A polytope $P$ in $\mathbb{R}^n$ is a generalized permutohedron if and only if its normal fan is refined by the braid arrangement fan.

Since we are moving the facets while keeping the normal vectors, we are simply changing the vector $\mathbf{b}$, and hence every generalized permutohedron is the set of solutions to a systems of inequalities of the form

$$M_n \mathbf{x} \ge \mathbf{z}$$

for some vector $\mathbf{z} \in V_n$. We assume all inequalities are tight (but not necessarily facet defining). Under this assumption every generalized permutohedron corresponds to a unique vector $\mathbf{z}$. Note that this forces $z_\emptyset = 0$.
However, not all vectors give a generalized permutohedron; it is possible to create unwanted edges. For our perturbation method we need to know a characterization of vectors that do give a generalized permutohedron. That is precisely the content of Theorem 1.7. For the completeness of the paper, we include a proof of the theorem.

**Proof of Theorem 1.7:**

*Only if:* We begin with the only if part. Suppose we have $z_I + z_J > z_{I \cap J} + z_{I \cup J}$ for some $I, J$. Then for any feasible $t$,

$$z_{I \cap J} + z_{I \cup J} < z_I + z_J \leq \sum_{i \in I} t_i + \sum_{j \in J} t_j = \sum_{i \in I \cap J} t_i + \sum_{j \in I \cup J} t_j$$

which means that for any point $t$ only one of the inequalities corresponding to $I \cap J$ and $I \cup J$ can be attained. Since all the inequalities are attained at some point, the above means that no point maximizes both of them at the same time. We now show this is not possible.

The two facets defined by the equations $\sum_{i \in I \cap J} t_i = z_{I \cap J}$ and $\sum_{j \in I \cup J} t_j = z_{I \cup J}$ meet in a ridge. In the braid arrangement the two corresponding edges span a two dimensional cone $F$ of the fan. By Proposition 2.8, the normal fan of $P_z$ is a coarsening of the braid arrangement, which means that each of its cones are unions of cones of the braid arrangement. The cone containing $F$ will correspond to a face which maximizes both $e_{I \cap J}$ and $e_{I \cup J}$, contradicting the first paragraph.

*If:* we assume all the inequalities $z_I + z_J \leq z_{I \cap J} + z_{I \cup J}$. Note that for any permutation $\omega \in S_n$ the intersection of the following $n$ supporting hyperplanes

$$\sum_{i \in [\omega(k)]} x_i = z_{[\omega(k)]} \quad \text{for all } k \in \{1, 2, \dots, n\}$$

where $[\omega(i)] := \{\omega(1), \omega(2), \dots, \omega(i)\}$ has unique solution $v_\omega \in \mathbb{R}^n$ with

$$(v_{\omega})_{\omega(i)} = z_{[\omega(i)]} - z_{[\omega(i-1)]}. \qquad (3)$$

In order to check they are all vertices, it is enough to verify that they satisfy all inequalities. We show it by induction on $|I|$. Without loss of generality we assume that $\omega = \text{id}$:

1. If $|I| = 1$ then we need to check that $v_i = z_{[i]} - z_{[(i-1)]} \geq z_{\{i\}}$ or equivalently $z_{[i]} \geq z_{\{i\}} + z_{[(i-1)]}$ which is true by the supermodular inequality.

2. If $I = \{i_1, i_2, \dots, i_k\}$ with $i_1 < i_2 < \dots < i_k$, we need to show

$$v_{i_1} + v_{i_2} + \dots + v_{i_{k-1}} + v_{i_k} \geq z_I$$

By induction we can bound the first $k-1$ terms by $z_{I-i_k}$, and, since $v_{i_k} = z_{[i_k]} - z_{[i_{k-1}]}$, we are done if we can show

$$z_{I-i_k} + z_{[i_k]} - z_{[i_{k-1}]} \geq z_I$$

Which is a direct application to the supermodular inequality to the sets $I$ and $[i_k - 1]$.
Now we need to verify that there are no other vertices. For this we use the greedy algorithm for
polymatroids which says that for any linear functional $c$ if we want to solve

$$
\begin{array}{ll}
\text{maximize} & c \cdot x \\
\text{subject to} & \displaystyle\sum_{i \in I} x_i \geq z_I \quad \forall I \subset [n] \\
& \displaystyle\sum_{i \in [n]} x_i = z_{[n]} \\
& x_i \in \mathbb{R}
\end{array}
$$

We can find an optimal $x^*$ in the following way. Fix a permutation $\omega$ of $[n]$ such that $c_{\omega(1)} \le c_{\omega(2)} \le \dots \le c_{\omega(n)}$ and then define

$$
x_{\omega(i)}^{*} = z_{[\omega(i)]} - z_{[\omega(i-1)]}
$$

as before. For a proof using weak duality see [13], chapter 44, page 771. This shows that all vertices are
the ones we already found above.

To finish, according to Definition 2.7, we need to show that vertices $v_{\omega}$ defined by (3) satisfies (2) with $k_{\omega,i} \ge 0$. However, by direct calculation, we get

$$
k_{\omega, i} = z_{[\omega(i+1)]} + z_{[\omega(i-1)]} - z_{[\omega(i-1)] \cup \omega(i+1)} - z_{\omega(i)} \ge 0,
$$

where the inequality follows from supermodularity.

<figure><img src="image_2.png" /></figure>

**Definition 2.9** For any $z$ in the interior of the super modular cone $C_n$, we call the corresponding generalized permutohedron generic.

**Remark 2.10** By definition, in a generic generalized permutohedron all the $2^n - 2$ inequalities defining it are facets. It follows that the generic generalized permutohedra are precisely the ones having the braid arrangement as their normal fan.

3 Exterior Formula

In 1975 Danilov, based on algebraic evidence, asked if it is possible to assign values to cones such that
the following *exterior formula* holds

$$
|P \cap \Lambda| = \sum_{F \text{:a face of } P} \mathrm{Vol}(F)\alpha(F, P) \quad (4)
$$

where $\Lambda$ is a lattice, and the volume is normalized and $\alpha(F, P)$ depends only on the tangent cone of $F$ in $P$.

McMullen [7] proved it was possible in a non constructive way. Berline and Vergne [3] were able to
construct such $\alpha$ in a computable way. Before giving more details of Berline-Vergne's construction, we
introduce some relevant definitions and results.

We assume the readers are familiar with the definition of algebra of polyhedra/polytopes and valuation
presented in [2].
**Definition 3.1** Suppose P is a polyhedron and F is a face. The tangent cone of F at P is:

$$tcone(F, P) = \{F + u : F + \delta u \in P \text{ for sufficiently small } \delta\}$$

The feasible cone of F at P is:

$$fcone(F, P) = \{u : F + \delta u \in P \text{ for sufficiently small } \delta\}$$

In order to always work with pointed cones, we also define

$$tcone^p(F, P) = tcone(F, P)/L \quad \text{and} \quad fcone^p(F, P) = fcone(F, P)/L$$

where L is the subspace spanned by F. Then $tcone^p(F, P)$ and $fcone^p(F, P)$ are pointed cones with dimension $\dim P - \dim F$.

Given a polyhedron $P \subseteq \mathbb{R}^n$ we define the indicator function $[P] : \mathbb{R}^n \to \mathbb{R}$ as:

$$[P](x) = 1 \text{ if } x \in P \text{ and zero otherwise.}$$

Below is an important result on feasible cones.

**Theorem 3.2 (Theorem 6.6 of [2])** Suppose P is a nonempty polytope. Then

$$[0] \equiv \sum_{v: \text{ a vertex of } P} fcone(v, P) \quad \text{modulo polyhedra with lines}$$

## 3.1 Berline-Vergne's construction

Berline and Vergne constructed in [3] a valuation $\Psi$ on rational cones and show it has the following properties

(P1) The exterior formula (4) holds if we set

$$\alpha(F, P) := \Psi(tcone^p(F, P)). \qquad (5)$$

(P2) If a cone C contains a line, then $\Psi(C) = 0$.

(P3) $\Psi$ is invariant under lattice translation, i.e., $\Psi(C) = \Psi(C + p)$ for any lattice point $p$.

(P4) Its value on a lattice point is 1, i.e. $\Psi([0]) = 1$

(P5) It can be computed in polynomial time fixing the dimension.

We have an immediate corollary to Property (P2), together with the fact that $\Psi$ is a valuation:

**Corollary 3.3** Suppose $K_1, K_2, \dots, K_k$ and $K$ are cones satisfying

$$[K] \equiv \sum_{i=1}^{k} [K_i] \quad \text{modulo polyhedra with lines.}$$

Then

$$\Psi([K]) = \sum_{i=1}^{k} \Psi([K_i]).$$
When the cone $K$ is unimodular, computations are greatly simplified. In small dimensions we can even give a simple closed expression for $\alpha$ of unimodular cones. Here $\text{co}(v_1, \dots, v_k)$ denotes the cone spanned by the vectors $v_1, \dots, v_k$.

**Lemma 3.4** If $K = \text{co}(u_1, u_2)$ where $u_1, u_2$ are a basis for the lattice $\Lambda$ then

$$ \Psi(K) = \frac{1}{4} + \frac{1}{12} \left( \frac{\langle u_1, u_2 \rangle}{\langle u_1, u_1 \rangle} + \frac{\langle u_1, u_2 \rangle}{\langle u_2, u_2 \rangle} \right) $$

**Lemma 3.5** If $K = \text{co}(u_1, u_2, u_3)$ where $u_1, u_2, u_3$ are a basis for the lattice $\Lambda$ then

$$ \Psi(K) = \frac{1}{8} + \frac{1}{24} \left( \frac{\langle u_1, u_2 \rangle}{\langle u_1, u_1 \rangle} + \frac{\langle u_1, u_2 \rangle}{\langle u_2, u_2 \rangle} + \frac{\langle u_1, u_3 \rangle}{\langle u_1, u_1 \rangle} + \frac{\langle u_1, u_3 \rangle}{\langle u_3, u_3 \rangle} + \frac{\langle u_3, u_2 \rangle}{\langle u_2, u_2 \rangle} + \frac{\langle u_3, u_2 \rangle}{\langle u_3, u_3 \rangle} \right) $$

**Remark 3.6** The apparent simplicity breaks down for dimension 4.

Recall the definition of $\alpha(F, P)$ in (5), we have the following lemma:

**Lemma 3.7** Suppose $P$ is a nonempty lattice polytope. Then

$$ \begin{align*} \sum_{v: \text{ a vertex of } P} \alpha(v, P) &= 1; \\ \alpha(P, P) &= 1; \\ \alpha(F, P) &= 1/2, \quad \text{for any facet } F \text{ of } P. \end{align*} $$

**Proof:** The first equality follows from applying the valuation $\Psi$ to the identity in Theorem 3.2, Corollary 3.3, and noticing that in a lattice polytope a tangent cone is a lattice translation of the corresponding feasible cone. The second equality follows from Property (P4).

The third equality follows from an analysis of the formula given in Lemma 3.4, which we omit. $\square$

## 3.2 Applications

One application of the exterior formula (4) is that it provides another way to prove Ehrhart’s theorem. Moreover, it gives a description of each Ehrhart coefficient. We state the following modified version of Theorem 1.1.

**Theorem 3.8** For a lattice polytope $P$,

$$ L_P(n) = |nP \cap \Lambda| $$

is a polynomial in $n$ of degree $\dim P$. Furthermore, the coefficient of $n^k$ in $L_P(n)$ is

$$ \sum_{F:\dim(F)=k} \alpha(F, P) \text{Vol}(F). \qquad (6) $$
**Proof:** When we dilate the polytope by a factor of $n$, each face $F$ of $P$ becomes $nF$, a face of $nP$. It is clear that the tangent/feasible cone does not change. Hence, applying the exterior formula to $nP$, we get

$$|nP \cap \Lambda| = \sum_F \mathrm{Vol}(nF)\alpha(nF, nP) = \sum_F \mathrm{Vol}(F)\alpha(F, P) n^{\dim F}.$$

Then our conclusion follows. □

The formula (6) for the coefficients of the Ehrhart polynomial $L_P(n)$ gives a sufficient condition for Ehrhart positivity. It is our first step to reduce conjecture 1.2 to conjecture 1.3.

**Lemma 3.9** Let $P$ be a lattice polytope. If for every face $F$ of $P$, we have $\alpha(F, P) > 0$, then $P$ is Ehrhart positive.

In the next section, we will apply the idea of perturbation to generalized permutohedra to finish the second step of reduction, and complete the proof for Theorem 1.4.

# 4 Perturbation of generalized permutohedra

We start with definitions and results on perturbation methods that will be used.

**Definition 4.1** Let $A$ be an $N \times D$ matrix and $b \in \mathbb{R}^N$. Suppose $P$ is a nonempty polyhedron in $\mathbb{R}^D$ defined by $Ax \le b$ and $b(t)$ is a continuous function on some interval containing 0 such that $b(0) = b$.

We say $b(t)$ provides a perturbation for $P$ if for each $t \ne 0$ in the interval, $b(t)$ defines a nonempty polyhedron $P(t) = \{x : Ax \le b(t)\}$ with exactly $l$ vertices: $w_{t,1}, \cdots, w_{t,l}$ and the feasible cone of $P(t)$ at $w_{t,j}$ does not depend on $t$, that is, for each $j : 1 \le j \le l$, there exists a fixed cone $K_j$ such that $\mathrm{fcone}(P(t), w_{t,j}) = K_j$ for all $t \ne 0$. (Note that this is equivalent to say that all $P(t)$ with $t \ne 0$ have the same normal fan.)

The following is a result in [6].

**Theorem 4.2** Suppose $b(t)$ provides a perturbation for the nonempty polyhedron $P$ and assume the setup is the same as in Definition 4.1. Then we have the following:

* For each fixed $j : 1 \le j \le l$, the set of vertices $\{w_{t,j}\}$ converges to some vertex of $P$ as $t$ goes to 0.

* For each vertex $v \in \mathrm{Vert}(P)$, let $J_v$ be the set of $j$'s where $\{w_{t,j}\}$ converges to $v$. Then

$$[\mathrm{fcone}(v, P)] \equiv \sum_{j \in J_v} [K_j] \quad \text{modulo polyhedra with lines}$$

The above theorem only deals with vertices and vertex cones. We will generalize it to all faces. We need a preliminary definition and observation: Assume the same setup as in Definition 4.1. We say a set $J \subseteq \{1, 2, \dots, l\}$ defines a face of $P(t)$ if $\mathrm{conv}(w_{t,j} | j \in J)$ is a face of $P(t)$. We observe that a set $J$ defines a face of $P(t_0)$ for some $t_0$ if and only if $J$ defines a face of $P(t)$ for all $t$. Therefore, when we say $J$ defines a face of $P(t)$, we mean it is true for all $t$ in the interval.

**Theorem 4.3** Suppose $b(t)$ provides a perturbation for the nonempty polyhedron $P$ and assume the setup is the same as in Definition 4.1. Then we have the following:
* For each set $J$ that defines a face $F(t)$ of $P(t)$, $F = \text{conv}\{\lim_{t\to 0} w_{t,j} | j \in J\}$ is a face of $P$. In this case, we say $F(t)$ converges to $F$.

* For each $F$ of $P$, let $F_1(t), F_2(t), \dots, F_k(t)$ be all the faces of $P(t)$ of dimension $\dim F$ that converge to $F$. Then

$$ [\text{fcone}^p(F, P)] \equiv \sum_{i=1}^{k} [\text{fcone}^p(F_i(t), P(t))] \quad \text{modulo polyhedra with lines} \quad (7) $$

When we restrict faces to be 0-dimensional in Theorem 4.3, we recover Theorem 4.2. The idea of the proof for Theorem 4.3 is to reduce the higher-dimensional faces to vertices, and then apply Theorem 4.2. We omit the proof from this extended abstract.

We will apply Theorem 4.3 to generalized permutohedra. First, for any generalized permutohedron $P_z$ given by $M_n\mathbf{x} \ge \mathbf{z}$, we would like to perturb it to obtain a generic generalized permutohedron. For this we appeal to Theorem 1.7.

**Proposition 4.4** Let $\mathbf{z} \in K_C$ be any vector in the supermodular cone. There exists a continuous function $\mathbf{z}(t)$ such that

$$ P_{\mathbf{z}(t)} = \{\mathbf{x} \in \mathbb{R}^n : M_n \mathbf{x} \ge \mathbf{z}(t)\} $$

is generic for $t > 0$ and $P_{\mathbf{z}(0)} = P_{\mathbf{z}}$.

**Proof:** Recall that by Remark 2.10 being generic is the same as being an interior point of $C_n$. By convexity, the line segment connecting $\mathbf{z}$ with any interior point is contained in the cone $K_C$. Furthermore every point in the segment, except for $\mathbf{z}$, is an interior point, hence the conclusion. $\square$

**Corollary 4.5** Let $\mathbf{z}(t)$ be a function satisfying the conditions in Proposition 4.4. Then for any face $F \subseteq P_z$, we have that $\alpha(F, P) = \sum_i \alpha(F_i, \Pi_n)$ for some set of faces $F_i$ of $\Pi_n$.

**Proof:** By Proposition 4.4, the hypothesis of Theorem 4.3 is satisfied with $A = M_n$, $b = \mathbf{z}$ and $b(t) = \mathbf{z}(t)$. Then it follows from (7) and Corollary 3.3 that for any $t \neq 0$, we have $\alpha(F, P) = \sum_i \alpha(F_i(t), P_{\mathbf{z}(t)})$ for some set of faces $F_i(t)$ of $P_{\mathbf{z}(t)}$. However, by the construction of $\mathbf{z}(t)$, $P_{\mathbf{z}(t)}$ is a generic generalized permutohedron, which has the same normal fan as $\Pi_n$. Then the conclusion follows. $\square$

We can finally present the proof of Theorem 1.4.

**Proof of Theorem 1.4;** By Lemma 3.9, in order to show a generalized permutohedra $P$ is Ehrhart positive, it is enough to show $\alpha(F, P)$ is positive for each face $F$ of $P$. However, by Corollary 4.5, the positivity of $\alpha$'s for $P$ follows from the positivity of $\alpha$'s for $\Pi_n$. $\square$

# 5 Regular Permutohedron

In this section we show how to compute the $\alpha$ for all faces of the regular permutohedron. There are two facts that will make this computations much easier than the general case:
1. Tangent cone at every vertex is unimodular. Even more, they are all the simple roots $A_n$.

2. Because of symmetry, it is enough to focus on one single tangent cone and all of its faces.

**Remark 5.1** Pommersheim and Thomas [9] gave another way of constructing the $\alpha$ values satisfying the exterior formula. Their construction depends on an ordering of a basis for the vector space. Berline and Vergne's construction is invariant under permutations of the basis. This is one of the reasons why we work with their construction for this particular case.

Let's do $\Pi_4$ in some detail.

We can center our attention to the vertex $v = (1, 2, 3, 4)$. Its tangent cone is

$$A_3 = \operatorname{span}((1, -1, 0, 0), (0, 1, -1, 0), (0, 0, 1, -1))$$

We will go through each face of this cone:

* The vertex itself. Its $\alpha$ value is equal to $1/24$, because by symmetry all vertices have the same value and they add up to 1 by Lemma 3.7.

* Edges. There are two types let's do the edge in direction $(1, -1, 0, 0)$ (the edge $(0, 0, 1, -1)$ gives the same value), which in the picture corresponds to an edge in a square.

First we need to compute its pointed tangent cone. Since $A_3$ is unimodular, this can be seen computed as the cone generated by $(0, 1, -1, 0), (0, 0, 1, -1)$ in $\mathbb{R}^4/\langle(1, -1, 0, 0), (1, 1, 1, 1)\rangle$. Their images are $(1/2, 1/2, -1, 0), (0, 0, 1, -1)$, and the cone they generate is unimodular in the lattice $\mathbb{Z}^4/\langle(1, -1, 0, 0), (1, 1, 1, 1)\rangle$. We are in position to apply lemma 3.4 and obtain a value of $11/72$.

The edge $(0, 1, -1, 0)$ is different, this correspond to an edge contained in two hexagons. In this case the value is $14/72$.

* Facets. They always have a value of $1/2$.

* The whole cone. Its value is always 1.

Applying the exterior formula

$$|\Pi_4 \cap \mathbb{Z}^4| = \sum_F \alpha(P, F)\operatorname{vol}(F)$$

we get the left hand side equal to:

$$24 \left( \frac{1}{24} \cdot 1 \right) + 24 \left( \frac{11}{72} \cdot 1 \right) + 12 \left( \frac{14}{72} \cdot 1 \right) + 6 \left( \frac{1}{2} \cdot 1 \right) + 8 \left( \frac{1}{2} \cdot 3 \right) + 1 (1 \cdot 16)$$

The terms correspond to the contribution of vertices, square edges, hexagonal edges, square faces, hexagonal faces (note they have normalized volume 3), and finally the whole polytope. This information gives the Ehrhart polynomial

$$1 + 6n + 15n^2 + 16n^3$$

The above computations have been carried out up to $\Pi_7$, verifying Conjecture 1.3 up to dimension six. We don't have a conjecture for the exact values, but in the computations, all faces of codimension $k$ have values close to $1/k!$. In the example above note that the edges corresponds to faces of codimension 2 of $A_3$, and their values $11/72$ and $14/72$ are close to $1/3! = 1/6 = 12/72$.
Acknowledgements

The authors thank Federico Ardila for discussions about generalized permutohedra, specially about Theorem 1.7. We also thank Michele Vergne for providing a code used in some of the computations.

References

[1] Federico Ardila, Carolina Benedetti, and Jeffrey Doker. Matroid polytopes and their volumes. *Discrete Comput. Geom.*, 43(4):841–854, 2010.

[2] Alexander Barvinok. *Integer points in polyhedra*. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), Zürich, 2008.

[3] Nicole Berline and Michèle Vergne. Local Euler-Maclaurin formula for polytopes. *Mosc. Math. J.*, 7(3):355–386, 573, 2007.

[4] Jesús A. De Loera, David C. Haws, and Matthias Köppe. Ehrhart polynomials of matroid polytopes and polymatroids. *Discrete Comput. Geom.*, 42(4):670–702, 2009.

[5] Fu Liu. Ehrhart polynomials of cyclic polytopes. *J. Combin. Theory Ser. A*, 111(1):111–127, 2005.

[6] Fu Liu. Perturbation of transportation polytopes. *J. Combin. Theory Ser. A*, 120(7):1539–1561, 2013.

[7] Peter McMullen. Valuations and dissections. In *Handbook of convex geometry*, Vol. A, B, pages 933–988. North-Holland, Amsterdam, 1993.

[8] Jason Morton, Lior Pachter, Anne Shiu, Bernd Sturmfels, and Oliver Wienand. Convex rank tests and semigraphoids. *SIAM J. Discrete Math.*, 23(3):1117–1134, 2009.

[9] James Pommersheim and Hugh Thomas. Cycles representing the Todd class of a toric variety. *J. Amer. Math. Soc.*, 17(4):983–994, 2004.

[10] Alex Postnikov, Victor Reiner, and Lauren Williams. Faces of generalized permutohedra. *Doc. Math.*, 13:207–273, 2008.

[11] Alexander Postnikov. Permutohedra, associahedra, and beyond. *Int. Math. Res. Not. IMRN*, (6):1026–1106, 2009.

[12] R. Rado. An inequality. *J. London Math. Soc.*, 27:1–6, 1952.

[13] Alexander Schrijver. *Combinatorial optimization. Polyhedra and efficiency*. Vol. B, volume 24 of *Algorithms and Combinatorics*. Springer-Verlag, Berlin, 2003. Matroids, trees, stable sets, Chapters 39–69.

[14] Richard P. Stanley. A zonotope associated with graphical degree sequences. In *Applied geometry and discrete mathematics*, volume 4 of *DIMACS Ser. Discrete Math. Theoret. Comput. Sci.*, pages 555–570. Amer. Math. Soc., Providence, RI, 1991.

[15] Richard P. Stanley and Jim Pitman. A polytope related to empirical distributions, plane trees, parking functions, and the associahedron. *Discrete Comput. Geom.*, 27(4):603–634, 2002.