# Ehrhart $h^*$-vectors of hypersimplices

Nan Li†

Department of Mathematics, Massachusetts Institute of Technology, 77 Mass Ave, Cambridge, MA 02139, USA

**Abstract.** We consider the Ehrhart $h^*$-vector for the hypersimplex. It is well-known that the sum of the $h_i^*$ is the normalized volume which equals an Eulerian number. The main result is a proof of a conjecture by R. Stanley which gives an interpretation of the $h_i^*$ coefficients in terms of descents and excedances. Our proof is geometric using a careful book-keeping of a shelling of a unimodular triangulation. We generalize this result to other closely related polytopes.

**Résumé.** Nous considérons que la Ehrhart $h^*$-vecteur pour la hypersimplex. il est bien connu que la somme de la $h_i^*$ est le volume normalisé qui est égal à un nombre eulérien. Le résultat principal est une preuve de la conjecture par R. Stanley qui donne une interprétation des coefficients $h_i^*$ en termes de descentes et excedances. Notre preuve est géométrique àl'aide d'un attention la comptabilité d'un bombardement d'une triangulation unimodulaire. Nous généralisons ce résultat à d'autres polytopes étroitement liés.

**Keywords:** Hypersimplex, Ehrhart $h^*$-vector, Shellable triangulation, Eulerian statistics

## 1 Introduction

Hypersimplices appear naturally in algebraic and geometric contexts. For example, they can be considered as moment polytopes for torus actions on Grassmannians or weight polytopes of the fundamental representations of the general linear groups $GL_n$. Fix two integers $0 < k \le n$. The $(k, n)$-th hypersimplex is defined as follows

$$ \bar{\Delta}_{k,n} = \{(x_1, \dots, x_n) \mid 0 \le x_1, \dots, x_n \le 1; x_1 + \dots + x_n = k\}, $$

or equivalently,

$$ \Delta_{k,n} = \{(x_1, \dots, x_{n-1}) \mid 0 \le x_1, \dots, x_{n-1} \le 1; k-1 \le x_1 + \dots + x_{n-1} \le k\}. $$

They can be considered as the slice of the hypercube $[0, 1]^{n-1}$ located between the two hyperplanes $\sum_{i=1}^{n-1} x_i = k-1$ and $\sum_{i=1}^{n-1} x_i = k$.

For a permutation $w \in \mathfrak{S}_n$, we call $i \in [n-1]$ a descent of $w$, if $w(i) > w(i+1)$. We define $\text{des}(w)$ to be the number of descents of $w$. We call $A_{k,n-1}$ the Eulerian number, which equals the number of permutations in $\mathfrak{S}_{n-1}$ with $\text{des}(w) = k-1$. The following result is well-known (see for example, [9, Exercise 4.59 (b)]).

<footnote>†Partially supported by the US National Science Foundation under Grant DMS-0604423.</footnote>
**Theorem 1.1 (Laplace)** *The normalized volume of $\Delta_{k,n}$ is the Eulerian number $A_{k,n-1}$.*

Let $S_{k,n}$ be the set of all points $(x_1, \dots, x_{n-1}) \in [0, 1]^{n-1}$ for which $x_i < x_{i+1}$ for exactly $k-1$ values of $i$ (including by convention $i=0$). Foata asked whether there is some explicit measure-preserving map that sends $S_{k,n}$ to $\Delta_{k,n}$. Stanley [6] gave such a map, which gave a triangulation of the hypersimplex into $A_{k,n-1}$ unit simplices and provided a geometric proof of Theorem 1.1. Sturmfels [10] gave another triangulation of $\Delta_{k,n}$, which naturally appears in the context of Gröbner bases. Lam and Postnikov [5] compared these two triangulations together with the alcove triangulation and the circuit triangulation. They showed that these four triangulations are identical. We call a triangulation of a convex polytope *unimodular* if every simplex in the triangulation has normalized volume one. It is clear that the above triangulations of the hypersimplex are unimodular.

Let $\mathcal{P} \in \mathbb{Z}^N$ be any $n$-dimensional integral polytope (its vertices are given by integers). Then Ehrhart's theorem tells us that the function

$$i(\mathcal{P}, r) := \#(r\mathcal{P} \cap \mathbb{Z}^N)$$

is a polynomial in $r$, and

$$\sum_{r \ge 0} i(\mathcal{P}, r) t^r = \frac{h^*(t)}{(1-t)^{n+1}},$$

where $h^*(t)$ is a polynomial in $t$ with degree $\le n$. We call $h^*(t)$ the $h^*$-polynomial of $\mathcal{P}$, and the vector $(h_0^*, \dots, h_n^*)$, where $h_i^*$ is the coefficient of $t^i$ in $h^*(t)$, is called the $h^*$-vector of $\mathcal{P}$. We denote its term by $h_i^*(\mathcal{P})$. It is known that the sum $\sum_{i=0}^n h_i^*(\mathcal{P})$ equals the normalized volume of $\mathcal{P}$.

Katzman [3] proved the following formula for the $h^*$-vector of the hypersimplex $\Delta_{k,n}$. In particular, we see that $\sum_{i=0}^n h_i^*(\Delta_{k,n}) = A_{k,n-1}$. Write $\binom{n}{\ell}$ to denote the coefficient of $t^\ell$ in $(1+t+t^2+\dots+t^{\ell-1})^n$. Then the $h^*$-vector of $\Delta_{k,n}$ is $(h_0^*(\Delta_{k,n}), \dots, h_{n-1}^*(\Delta_{k,n}))$, where for $d=0, \dots, n-1$

$$h_d^*(\Delta_{k,n}) = \sum_{i=0}^{k-1} (-1)^i \binom{n}{i} \binom{n}{k-i} \qquad (1)$$

Moreover, since all the $h_i^*(\Delta_{k,n})$ are nonnegative integers ([7]) (this is not clear from (1)), it will be interesting to give a combinatorial interpretation of the $h_i^*(\Delta_{k,n})$.

The *half-open hypersimplex* $\Delta'_{k,n}$ is defined as follows. If $k > 1$,

$$\Delta'_{k,n} = \{(x_1, \dots, x_{n-1}) \mid 0 \le x_1, \dots, x_{n-1} \le 1; k-1 < x_1 + \dots + x_{n-1} \le k\},$$

and

$$\Delta'_{1,n} = \Delta_{1,n}.$$

We call $\Delta'_{k,n}$ “half-open” because it is basically the normal hypersimplex with the “lower” facet removed. From the definitions, it is clear that the volume formula and triangulations of the usual hypersimplex $\Delta_{k,n}$ also work for the half-open hypersimplex $\Delta'_{k,n}$, and it is nice that for fixed $n$, the half-open hypersimplices $\Delta'_{k,n}$, for $k=1, \dots, n-1$, form a disjoint union of the hypercube $[0, 1]^{n-1}$. From the following formula for the $h^*$-polynomial of the half-open hypersimplices, we can compute the $h^*$-polynomial of the usual hypersimplices inductively. Also, we can compute its Ehrhart polynomial.

For a permutation $w$, we call $i$ an *excedance* of $w$ if $w(i) > i$ (a *reversed excedance* if $w(i) < i$). We denote by $\mathrm{exc}(w)$ the number of excedances of $w$. The main theorems of the paper are the following.
**Theorem 1.2** The h*-polynomial of the half-open hypersimplex $\Delta'_{k,n}$ is given by

$$ \sum_{\substack{w \in \mathfrak{S}_{n-1} \\ \mathrm{exc}(w)=k-1}} t^{\mathrm{des}(w)}. $$

We prove this theorem first by a generating function method (in Section 2) and second by a geometric method, i.e., giving a shellable triangulation of the hypersimplex (in Sections 4). In Section 3, we will provide some background.

We can define a different shelling order on the triangulation of $\Delta'_{k,n}$, and get another expression of its h*-polynomial using descents and a new permutation statistic called *cover* (see its definition in Lemma 5.4).

**Theorem 1.3** The h*-polynomial of $\Delta'_{k,n}$ is

$$ \sum_{\substack{w \in \mathfrak{S}_{n-1} \\ \mathrm{des}(w)=k-1}} t^{\mathrm{cover}(w)}. $$

Combining Theorem 1.3 with Theorem 1.2, we have the equal distribution of (exc, des) and (des, cover):

**Corollary 1.4**

$$ \sum_{w \in \mathfrak{S}_n} t^{\mathrm{des}(w)} x^{\mathrm{cover}(w)} = \sum_{w \in \mathfrak{S}_n} t^{\mathrm{exc}(w)} x^{\mathrm{des}(w)}. $$

Finally, we study the generalized hypersimplex $\Delta_{k,\alpha}$ (see definition in Section 6). This polytope is related to algebras of Veronese type. For example, it is known [1] that every algebra of Veronese type coincides with the Ehrhart ring of a polytope $\Delta_{k,\alpha}$. We can extend the second shelling to the generalized hypersimplex $\Delta'_{k,\alpha}$ (defined in (6)), and express its h*-polynomial in terms of a colored version of descents and covers (see Theorem 6.2). This extended abstract is based on [4], where you can find more details.

## 2 Proof of Theorem 1.2 by generating functions

Here is a proof of this theorem using generating functions.

**Proof:** Suppose we can show that

$$ \sum_{r \ge 0} \sum_{k \ge 0} \sum_{n \ge 0} i(\Delta'_{k+1,n+1}, r) u^n s^k t^r = \sum_{n \ge 0} \sum_{\sigma \in \mathfrak{S}_n} t^{\mathrm{des}(\sigma)} s^{\mathrm{exc}(\sigma)} \frac{u^n}{(1-t)^{n+1}}. \quad (2) $$

By considering the coefficient of $u^n s^k$ in (2), we have

$$ \sum_{r \ge 0} i(\Delta'_{k+1, n+1}, r) t^r = (1-t)^{-(n+1)} \left( \sum_{\substack{w \in \mathfrak{S}_n \\ \mathrm{exc}(w)=k}} t^{\mathrm{des}(w)} \right), $$
which implies Theorem 1.2. By the following equation due to Foata and Han [2, Equation (1.15)],

$$ \sum_{n \ge 0} \sum_{\sigma \in \mathfrak{S}_n} t^{\text{des}(\sigma)} s^{\text{exc}(\sigma)} \frac{u^n}{(1-t)^{n+1}} = \sum_{r \ge 0} t^r \frac{1-s}{(1-u)^{r+1}(1-us)^{-r}-s(1-u)}, $$

we only need to show that

$$ \sum_{k \ge 0} \sum_{n \ge 0} i(\Delta'_{k+1,n+1}, r) u^n s^k = \frac{1-s}{(1-u)^{r+1}(1-us)^{-r}-s(1-u)}. $$

By the definition of the half-open hypersimplex, we have, for any $r \in \mathbb{Z}_{\ge 0}$,

$$ r\Delta'_{k+1,n+1} = \{(x_1, \dots, x_n) \mid 0 \le x_1, \dots, x_n \le r, rk+1 \le x_1 + \dots + x_n \le (k+1)r\}, $$

if $k > 0$, and for $k = 0$,

$$ r\Delta'_{1,n+1} = \{(x_1, \dots, x_n) \mid 0 \le x_1, \dots, x_n \le r, 0 \le x_1 + \dots + x_n \le r\}. $$

So

$$ i(\Delta'_{k+1,n+1}, r) = ([x^{kr+1}] + \dots + [x^{(k+1)r}]) \left(\frac{1-x^{r+1}}{1-x}\right)^n, \quad (3) $$

if $k > 0$, and when $k = 0$, we have

$$ i(\Delta'_{1,n+1}, r) = ([x^0] + [x] + \dots + [x^r]) \left(\frac{1-x^{r+1}}{1-x}\right)^n, \quad (4) $$

where the notation $[x^i]f(x)$ for some power series $f(x)$ denotes the coefficient of $x^i$ in $f(x)$. Notice that the case of $k = 0$ is different from $k > 0$ and $i(\Delta'_{1,n+1}, r)$ is obtained by evaluating $k = 0$ in (3) plus an extra term $[x^0]\left(\frac{1-x^{r+1}}{1-x}\right)^n$. Since the coefficient of $x^k$ of a function $f(x)$ equals the constant term of $\frac{f(x)}{x^k}$, we have

$$ \begin{aligned} & ([x^{kr+1}] + \dots + [x^{(k+1)r}]) \left(\frac{1-x^{r+1}}{1-x}\right)^n = [x^0] \left(\frac{1-x^{r+1}}{1-x}\right)^n (x^{-kr-1} + \dots + x^{-(k+1)r}) \\ &= [x^{kr}] \left(\frac{1-x^{r+1}}{1-x}\right)^n (x^{-kr-1} + \dots + x^{-(k+1)r}) x^{kr} \\ &= [x^{kr}] \frac{(1-x^r)(1-x^{r+1})^n}{(1-x)^{n+1}x^r}. \end{aligned} $$

So we have, for $k > 0$,

$$ \begin{aligned} \sum_{n \ge 0} i(\Delta'_{k+1,n+1}, r) u^n &= \sum_{n \ge 0} [x^{kr}] \frac{(1-x^r)(1-x^{r+1})^n}{(1-x)^{n+1}x^r} u^n \\ &= [x^{kr}] \frac{(1-x^r)}{(1-x)x^r} \sum_{n \ge 0} \left( \frac{(1-x^{r+1})u}{1-x} \right)^n \\ &= [x^{kr}] \frac{x^r - 1}{x^r(u-ux^{r+1}-1+x)}. \end{aligned} $$
For $k=0$, based on the difference between (3) and (4) observed above, we have:

$$ 
\begin{aligned}
\sum_{n \ge 0} i(\Delta'_{1,n+1}, r) u^n &= \sum_{n \ge 0} [x^0] \frac{(1-x^r)(1-x^{r+1})^n}{(1-x)^{n+1}x^r} u^n + \sum_{n \ge 0} [x^0] \left( \frac{1-x^{r+1}}{1-x} \right)^n u^n \\
&= \left( [x^0] \frac{x^r-1}{x^r(u-ux^{r+1}-1+x)} \right) + \frac{1}{1-u}.
\end{aligned}
$$

So

$$ \sum_{k \ge 0} \sum_{n \ge 0} i(\Delta'_{k+1,n+1}, r) u^n s^k = \left( \sum_{k \ge 0} [x^{kr}] \frac{x^r - 1}{x^r(u - u x^{r+1} - 1 + x)} s^k \right) + \frac{1}{1-u}. $$

Let $y = x^r$. We have

$$ \sum_{k \ge 0} \sum_{n \ge 0} i(\Delta'_{k+1,n+1}, r) u^n s^k = \sum_{k \ge 0} [x^{kr}] \frac{y-1}{y(u-uxy-1+x)} s^k + \frac{1}{1-u}. $$

Expand $\frac{y-1}{y(u-uxy-1+x)}$ in powers of $x$, we have

$$ 
\begin{aligned}
\frac{y-1}{y(u-uxy-1+x)} &= \frac{y-1}{y} \cdot \frac{1}{u-1-(uxy-x)} \\
&= \frac{y-1}{y(u-1)} \cdot \frac{1}{1-\frac{x(uy-1)}{u-1}} \\
&= \frac{1-y}{y(1-u)} \sum_{i \ge 0} \left( \frac{(1-uy)x}{1-u} \right)^i.
\end{aligned}
$$

Since we only want the coefficient of $x^i$ such that $r$ divides $i$, we get

$$ 
\begin{aligned}
\frac{1-y}{y(1-u)} \sum_{j \ge 0} \left( \frac{(1-uy)x}{1-u} \right)^{rj} &= \frac{1-y}{y(1-u)} \cdot \frac{1}{1-\frac{(1-uy)^r x^r}{(1-u)^r}} \\
&= \frac{1-y}{y(1-u)} \cdot \frac{(1-u)^r}{(1-u)^r - (1-uy)^r x^r} \\
&= \frac{(1-u)^{r-1}(1-y)}{y(1-u)^r - y^2(1-yu)^r}.
\end{aligned}
$$

So

$$ \sum_{k \ge 0} \sum_{n \ge 0} i(\Delta'_{k+1,n+1}, r) u^n s^k = \left( \sum_{k \ge 0} s^k [y^k] \frac{(1-u)^{r-1}(1-y)}{y(1-u)^r - y^2(1-yu)^r} \right) + \frac{1}{1-u}. $$
To remove all negative powers of $y$, we do the following expansion

$$ 
\begin{aligned}
\frac{(1-u)^{r-1}(1-y)}{y(1-u)^r - y^2(1-yu)^r} &= \frac{1-y}{(1-u)y} \cdot \frac{1}{1 - \frac{y(1-yu)^r}{(1-u)^r}} \\
&= \sum_{i \ge 0} \left( \frac{y^{i-1}(1-uy)^{ri}}{(1-u)^{ri+1}} - \frac{y^i(1-uy)^{ri}}{(1-u)^{ri+1}} \right) \\
&= \frac{1}{1-u} y^{-1} + \text{nonnegative powers of } y.
\end{aligned}
$$

Notice that $\sum_{k \ge 0} s^k[y^k] \frac{(1-u)^{r-1}(1-y)}{y(1-u)^r - y^2(1-yu)^r}$ is obtained by taking the sum of nonnegative powers of $y$ in $\frac{(1-u)^{r-1}(1-y)}{y(1-u)^r - y^2(1-yu)^r}$ and replacing $y$ by $s$. So

$$ \sum_{k \ge 0} s^k[y^k] \frac{(1-u)^{r-1}(1-y)}{y(1-u)^r - y^2(1-yu)^r} = \frac{(1-u)^{r-1}(1-s)}{s(1-u)^r - s^2(1-su)^r} - \frac{1}{s(1-u)}. $$

Therefore,

$$ 
\begin{aligned}
\sum_{k \ge 0} \sum_{n \ge 0} i(\Delta'_{k+1,n+1}, r) u^n s^k &= \frac{(1-u)^{r-1}(1-s)}{s(1-u)^r - s^2(1-su)^r} - \frac{1}{s(1-u)} + \frac{1}{1-u} \\
&= \frac{1-s}{(1-u)^{r+1}(1-us)^{-r} - s(1-u)}.
\end{aligned}
$$

□

# 3 Background

## 3.1 Shellable triangulation and the $h^*$-polynomial

Let $\Gamma$ be a triangulation of an $n$-dimensional polytope $\mathcal{P}$, and let $\alpha_1, \dots, \alpha_s$ be an ordering of the simplices (maximal faces) of $\Gamma$. We call $(\alpha_1, \dots, \alpha_s)$ a *shelling* of $\Gamma$ [7], if for each $2 \le i \le s$, $\alpha_i \cap (\alpha_1 \cup \dots \cup \alpha_{i-1})$ is a union of facets ((n-1)-dimensional faces) of $\alpha_i$. For example, (ignore the letters $A$, $B$, and $C$ for now) $\Gamma_1$ is a shelling, while any order starting with $\Gamma_2$ cannot be a shelling.

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

An equivalent condition (see e.g., [8]) for a shelling is that every simplex has a *unique minimal non-face*, where by a “non-face”, we mean a face that has not appeared in previous simplices. For example, for $\alpha_2 \in \Gamma_1$, the vertex $A$ is its unique minimal non-face, while for $\alpha_2 \in \Gamma_2$, both $B$ and $C$ are minimal and have not appeared before $\alpha_2$. We call a triangulation with a shelling a *shellable triangulation*. Given a shellable triangulation $\Gamma$ and a simplex $\alpha \in \Gamma$, define the *shelling number* of $\alpha$ (denoted by $\#(\alpha)$) to be
the number of facets shared by $\alpha$ and some simplex preceding $\alpha$ in the shelling order. For example, in $\Gamma_1$, we have

$$ \#(\alpha_1) = 0, \#(\alpha_2) = 1, \#(\alpha_3) = 1, \#(\alpha_4) = 2. $$

The benefit of having a shelling order for Theorem 1.2 comes from the following result.

**Theorem 3.1 ([7] Shelling and Ehrhart polynomial)** Let $\Gamma$ be a unimodular shellable triangulation of an $n$-dimensional polytope $\mathcal{P}$. Then

$$ \sum_{r \ge 0} i(\mathcal{P}, r) t^r = \left( \sum_{\alpha \in \Gamma} t^{\#(\alpha)} \right) (1-t)^{-(n+1)}. $$

## 3.2 Excedances and descents

Let $w \in \mathfrak{S}_n$. Define its standard representation of cycle notation to be a cycle notation of $w$ such that the first element in each cycle is its largest element and the cycles are ordered with their largest elements increasing. We define the cycle type of $w$ to be the composition of $n$: $C(w) = (c_1, \dots, c_k)$ where $c_i$ is the length of the $i$th cycle in its standard representation. The Foata map $F: w \to \hat{w}$ maps $w$ to $\hat{w}$ obtained from $w$ by removing parentheses from the standard representation of $w$. For example, consider a permutation $w: [5] \to [5]$ given by $w(1) = 5, w(2) = 1, w(3) = 4, w(4) = 3$ and $w(5) = 2$ or in one line notation $w = 51432$. Its standard representation of cycle notation is $(43)(521)$, so $\hat{w} = 43521$. The inverse Foata map $F^{-1}: \hat{w} \to w$ allows us to go back from $\hat{w}$ to $w$ as follows: first insert a left parenthesis before every left-to-right maximum and then close each cycle by inserting a right parenthesis accordingly. In the example, the left-to-right maximums of $\hat{w} = 43521$ are 4 and 5, so we get back $(43)(521)$. Based on the Foata map, we have the following result for the equal distribution of excedances and descents.

**Theorem 3.2 (Excedances and descents)** The number of permutations in $\mathfrak{S}_n$ with $k$ excedances equals the number of permutations in $\mathfrak{S}_n$ with $k$ descents.

## 3.3 Triangulation of the hypersimplex

We start from a unimodular triangulation $\{t_w | w \in \mathfrak{S}_n\}$ of the hypercube, where

$$ t_w = \{(y_1, \dots, y_n) \in [0, 1]^n \mid y_{w_1} \le y_{w_2} \le \dots \le y_{w_n}\}. $$

It is easy to see that $t_w$ has the following $n+1$ vertices: $v_0 = (0, \dots, 0)$, and $v_i = (y_1, \dots, y_n)$ given by $y_{w_1} = \dots = y_{w_{n-i}} = 0$ and $y_{w_{n-i+1}} = \dots = y_{w_n} = 1$. It is clear that $v_{i+1} = v_i + e_{w_{n-i}}$. Now define the following map $\phi$ ([6],[5]) that maps $t_w$ to $s_w$, a simplex in $\Delta_{k+1,n+1}$, sending $(y_1, \dots, y_n)$ to $(x_1, \dots, x_n)$, where

$$ x_i = \begin{cases} y_i - y_{i-1}, & \text{if } (w^{-1})_i > (w^{-1})_{i-1}, \\ 1 + y_i - y_{i-1}, & \text{if } (w^{-1})_i < (w^{-1})_{i-1}, \end{cases} \qquad (5) $$

where we set $y_0 = 0$. For each point $(x_1, \dots, x_n) \in s_w$, set $x_{n+1} = k+1 - (x_1 + \dots + x_n)$. Since $v_{i+1}$ and $v_i$ only differ in $y_{w_{n-i}}$, by (5), $\phi(v_i)$ and $\phi(v_{i+1})$ only differ in $x_{w_{n-i}}$ and $x_{w_{n-i+1}}$. More explicitly, we have

**Lemma 3.3** Denote $w_{n-i}$ by $r$. For $\phi(v_i)$, we have $x_r x_{r+1} = 01$ and for $\phi(v_{i+1})$, we have $x_r x_{r+1} = 10$. In other words, from $\phi(v_i)$ to $\phi(v_{i+1})$, we move a 1 from the $(r+1)$th coordinate forward by one coordinate.
**Proof:** First, we want to show that for $\phi(v_i)$, we have $x_r = 0$ and $x_{r+1} = 1$. We need to look at the segment $y_{r-1}y_r y_{r+1}$, of $v_i$. We know that $y_r = 0$, so there are four cases for $y_{r-1}y_r y_{r+1}: 000, 001, 100, 101$. If $y_{r-1}y_r y_{r+1} = 000$ for $v_i$, then $y_{r-1}y_r y_{r+1} = 010$ for $v_{i+1}$. Therefore, $w_{r-1}^{-1} < w_r^{-1} > w_{r+1}^{-1}$. Then by (5), we have $x_r x_{r+1} = 01$. Similarly, we can check in the other three cases that $x_r x_{r+1} = 01$ for $\phi(v_i)$.

Similarly, we can check the four cases for $y_{r-1}y_r y_{r+1}: 010, 011, 110, 111$ in $\phi(v_{i+1})$ and get $x_r x_{r+1} = 10$ in all cases. $\square$

Let $\text{des}(w^{-1}) = k$. It follows from Lemma 3.3 that the sum of the coordinates $\sum_{i=1}^n x_i$ for each vertex $\phi(v_i)$ of $s_w$ is either $k$ or $k+1$. So we have the triangulation [6] of the hypersimplex $\Delta_{k+1,n+1}: \Gamma_{k+1,n+1} = \{s_w | w \in \mathfrak{S}_n, \text{des}(w^{-1}) = k\}$.

Now we consider a graph $G_{k+1,n+1}$ on the set of simplices in the triangulation of $\Delta_{k+1,n+1}$. There is an edge between two simplices $s$ and $t$ if and only if they are adjacent (they share a common facet). We can represent each vertex of $G_{k+1,n+1}$ by a permutation and describe each edge of $G_{k+1,n+1}$ in terms of permutations [5]. We call this new graph $\Gamma_{k+1,n+1}$. It is clear that $\Gamma_{k+1,n+1}$ is isomorphic to $G_{k+1,n+1}$.

**Proposition 3.4 (5, Lemma 6.1 and Theorem 7.1)** *The graph $\Gamma_{k+1,n+1}$ can be described as follows: its vertices are permutations $u = u_1 \dots u_n \in \mathfrak{S}_n$ with $\text{des}(u^{-1}) = k$. There is an edge between $u$ and $v$, if and only if one of the following two holds:*

1. (type one edge) $u_i - u_{i+1} \neq \pm 1$ for some $i \in \{1, \dots, n-1\}$, and $v$ is obtained from $u$ by exchanging $u_i, u_{i+1}$.

2. (type two edge) $u_n \neq 1, n$, and $v$ is obtained from $u$ by moving $u_n$ to the front of $u_1$, i.e., $v = u_n u_1 \dots u_{n-1}$; or this holds with $u$ and $v$ switched.

**Example 3.5** Here is the graph $\Gamma_{3,5}$ for $\Delta'_{3,5}$.

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

In the above graph, the edge $\alpha$ between $u = 2413$ and $v = 4213$ is a type one edge with $i = 1$, since $4-2 \neq \pm 1$ and one is obtained from the other by switching 2 and 4; the edge $\beta$ between $u = 4312$ and $v = 2431$ is a type two edge, since $u_4 = 2 \neq 1, 4$ and $v = u_4 u_1 u_2 u_3$. The dotted line attached to a simplex $s$ indicates that $s$ is adjacent to some simplex $t$ in $\Delta_{2,5}$. Since we are considering the half-open hypersimplices, the common facet $s \cap t$ is removed from $s$.
# 4 Proof (outline) of Theorem 1.2 by a shellable triangulation

We want to show that the h*-polynomial of $\Delta'_{k+1,n+1}$ is

$$ \sum_{\substack{w \in \mathfrak{S}_n \\ \mathrm{exc}(w) = k}} t^{\mathrm{des}(w)}. $$

Compare this to Theorem 3.1: if $\Delta'_{k+1,n+1}$ has a shellable unimodular triangulation $\Gamma_{k+1,n+1}$, then its h*-polynomial is

$$ \sum_{\alpha \in \Gamma_{k+1,n+1}} t^{\#(\alpha)}. $$

We will define a shellable unimodular triangulation $\Gamma_{k+1,n+1}$ for $\Delta'_{k+1,n+1}$, label each simplex $\alpha \in \Gamma_{k+1,n+1}$ by a permutation $w_\alpha \in \mathfrak{S}_n$ with $\mathrm{exc}(w_\alpha) = k$. Then show that $\#(\alpha) = \mathrm{des}(w_\alpha)$.

We start from the triangulation $\Gamma_{k+1,n+1}$ studied in Section 3.3. By Proposition 3.4, each simplex is labeled by a permutation $u \in \mathfrak{S}_n$ with $\mathrm{des}(u^{-1}) = k$. Based on the Foata map defined in Section 3.2, we can use a sequence of maps and get a graph $S_{k+1,n+1}$ with vertices being permutations in $\mathfrak{S}_n$ with $k$ excedances. Applying the above maps to vertices of $\Gamma_{k+1,n+1}$, we call the new graph $S_{k+1,n+1}$. We will define the shelling order on the simplices in the triangulation by orienting each edge in the graph $S_{k+1,n+1}$. If we orient an edge $(u, v)$ such that the arrow points to $u$, then in the shelling, let the simplex labeled by $u$ be after the simplex labeled by $v$. We can orient each edge of $S_{k+1,n+1}$ such that the directed graph is acyclic. This digraph therefore defines a partial order on the simplices of the triangulation. We can prove that any linear extension of this partial order gives a shelling order. Given any linear extension obtained from the digraph, the shelling number of each simplex is the number of incoming edges. Let $w_\alpha$ be the permutation in $S_{k+1,n+1}$ corresponding to the simplex $\alpha$. Then we can show that for each simplex, its number of incoming edges equals $\mathrm{des}(w_\alpha)$. We will leave out the details here.

# 5 Proof of Theorem 1.3: second shelling

We want to show that the h*-polynomial of $\Delta'_{k+1,n+1}$ is also given by

$$ \sum_{\substack{w \in \mathfrak{S}_n \\ \mathrm{des}(w) = k}} t^{\mathrm{cover}(w)}, $$

we will define cover in a minute. Compare this to Theorem 3.1: if $\Delta'_{k+1,n+1}$ has a shellable unimodular triangulation $\Gamma_{k+1,n+1}$, then its h*-polynomial is

$$ \sum_{\alpha \in \Gamma_{k+1,n+1}} t^{\#(\alpha)}. $$

Similar to the proof of Theorem 1.2, we will define shellable unimodular triangulation for $\Delta'_{k+1,n+1}$, but this shelling is different from the one we use for Theorem 1.2. Label each simplex $\alpha \in \Gamma_{k+1,n+1}$ by a permutation $w_\alpha \in \mathfrak{S}_n$ with $\mathrm{des}(w_\alpha) = k$. Then show that $\#(\alpha) = \mathrm{cover}(w_\alpha)$.
We start from the graph $\Gamma_{k+1,n+1}$ studied in Section 3.3. Define a graph $M_{k+1,n+1}$ such that $w \in V(M_{k+1,n+1})$ if and only if $w^{-1} \in V(\Gamma_{k+1,n+1})$ and $(w, u) \in E(M_{k+1,n+1})$ if and only if $(w^{-1}, u^{-1}) \in E(\Gamma_{k+1,n+1})$. By Proposition 3.4, we have

$$V(M_{k+1,n+1}) = \{w \in \mathfrak{S}_n \mid \mathrm{des}(w) = k\},$$

and $(w, u) \in E(M_{k+1,n+1})$ if and only if $w$ and $u$ are related in one of the following ways:

1. type one: exchanging the letters $i$ and $i + 1$ if these two letters are not adjacent in $w$ and $u$

2. type two: one is obtained by subtracting 1 from each letter of the other (1 becomes $n-1$).

Now we want to orient the edges of $M_{k+1,n+1}$ to make it a digraph. Consider $e = (w, u) \in E(M_{k+1,n+1})$.

1. if $e$ is of type one, and $i$ is before $i + 1$ in $w$, i.e., $\mathrm{inv}(w) = \mathrm{inv}(u) - 1$, then orient the edge as $w \leftarrow u$.

2. if edge $(w, u)$ is of type two, and $v$ is obtained by subtracting 1 from each letter of $u$ (1 becomes $n-1$), then orient the edge as $w \leftarrow u$.

**Example 5.1** Here is the directed graph $M_{3,5}$ for $\Delta'_{3,5}$:

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

**Lemma 5.2** There is no cycle in the directed graph $M_{k+1,n+1}$.

Therefore, $M_{k+1,n+1}$ defines a poset on $V(M_{k+1,n+1})$ and $M_{k+1,n+1}$ is the Hasse diagram of the poset, which we still denote as $M_{k+1,n+1}$.

For an element in the poset $M_{k+1,n+1}$, the larger its rank is, the further its corresponding simplex is from the origin. More precisely, notice that each $v = (x_1, \dots, x_n) \in V_{k+1,n+1} = \Delta_{k+1,n+1} \cap \mathbb{Z}^n$ has $|v| = \sum_{i=1}^n x_i = k$ or $k + 1$. For $u \in M_{k+1,n+1}$, by which we mean $u \in V(M_{k+1,n+1})$, define $A_u = \#\{v \text{ is a vertex of the simplex } s_{u-1} \mid |v| = k+1\}$.

**Proposition 5.3** Let $w > u$ in the above poset $M_{k+1,n+1}$. Then $A_w \ge A_u$.

This proposition follows from a lemma proving that $A_u = u_n$, and the definition of the two types of directed edges.

We define the *cover* of a permutation $w \in M_{k+1,n+1}$ to be the number of permutations $v \in M_{k+1,n+1}$ it covers, i.e., the number of incoming edges of $w$ in the graph $M_{k+1,n+1}$. From the above definition, we have the following, (in the half-open setting):
**Lemma 5.4** 1. If $w_1 = 1$, then $\text{cover}(w) = \#\{i \in [n-1] \mid (w^{-1})_i + 1 < (w^{-1})_{i+1}\}$;

2. if $w_1 \neq 1$, then $\text{cover}(w) = \#\{i \in [n-1] \mid (w^{-1})_i + 1 < (w^{-1})_{i+1}\} + 1$.

**Proposition 5.5** Any linear extension of the above ordering gives a shelling order on the triangulation of $\Delta'_{k+1,n+1}$.

It is clear that the shelling number of the simplex corresponding to $w$ is $\text{cover}(w)$. Then by Theorem 3.1 and Proposition 5.5, we have a proof of Theorem 1.3.

# 6 The h*-polynomial for generalized half-open hypersimplex

We want to extend Theorem 1.3 to the hyperbox $B = [0, a_1] \times \dots \times [0, a_n]$. Write $\alpha = (a_1, \dots, a_n)$, $a_i \in \mathbb{Z}_{>0}$ and define the generalized half-open hypersimplex as

$$ \Delta'_{k,\alpha} = \{(x_1, \dots, x_n) \mid 0 \le x_i \le a_i; k-1 < x_1 + \dots + x_n \le k\}. \quad (6) $$

Note that the above polytope is a multi-hypersimplex studied in [5]. For a nonnegative integral vector $\beta = (b_1, \dots, b_n)$, let $C_\beta = \beta + [0, 1]^n$ be the cube translated from the unit cube by the vector $\beta$. We call $\beta$ the color of $C_\beta$.

We extend the triangulation of the unit cube to $B$ by translation and assign to each simplex in $B$ a colored permutation

$$ w_{\beta} \in \mathfrak{S}_{\alpha} = \{w \in \mathfrak{S}_n \mid b_i < a_i, i = 1, \dots, n\}. $$

Let $F_i = \{x_i = 0\} \cap [0, 1]^n$ for $i = 1, \dots, n$. Define the exposed facets for the simplex $s_{u-1}$ in $[0, 1]^n$ to be $\text{Expose}(u) = \{i \mid s_{u-1} \cap F_i$ is a facet of $s_{u-1}\}$.

We can compute $\text{Expose}(u)$ explicitly as follows.

**Lemma 6.1** Set $u_0 = 0$. Then $\text{Expose}(u) = \{i \in [n] \mid u_{i-1} + 1 = u_i\}$.

Now we want to extend the second shelling on the unit cube to the larger rectangle. In this extension, $F_i$ will be removed from $C_\beta$ if $b_i \neq 0$. Therefore, for the simplex $s_{w_\beta}$, we will remove the facet $F_i \cap s_{w_\beta}$ for each $i \in \text{Expose}(w) \cap \{i \mid b_i \neq 0\}$ as well as the cover($w_\beta$) facets for neighbors within $C_\beta$. We call this set $\text{Expose}(w) \cap \{i \mid b_i \neq 0\}$ the colored exposed facet (CEF), denoted by CEF($w_\beta$), for each colored permutation $w_\beta = (w, \beta)$.

Based on the above extended shelling, with some modifications of Proposition 5.5, we can show that the above order is a shelling order. Then, by Theorem 3.1 and the fact that the shelling number for $w_\beta$ is $\text{cover}(w_\beta) + \text{cef}(w_\beta)$, we have the following theorem.

**Theorem 6.2** The h*-polynomial for $\Delta'_{k,\alpha}$ is

$$ \sum_{\substack{w_{\beta} \in \mathfrak{S}_{\alpha} \\ \text{des}(w) + |\beta| = k-1}} t^{\text{cover}(w_{\beta}) + \text{cef}(w_{\beta})}. $$

We have some interesting identities about exc, des, cover and Expose.

**Proposition 6.3** For any $k \in [n-1]$, we have

$$ 1. \ \#\{w \in \mathfrak{S}_n \mid \text{exc}(w) = k, \text{des}(w) = 1\} = \binom{n}{k+1}. $$
2. {$w \in \mathfrak{S}_n \mid \mathrm{des}(w) = k, \mathrm{cover}(w) = 1$} = {$w \in \mathfrak{S}_n \mid \# \mathrm{Expose}(w) = n - (k+1)$}.

3. {$w \in \mathfrak{S}_n \mid \mathrm{des}(w) = k, \mathrm{cover}(w) = 1, \mathrm{Expose}(w) = S$} = 1, for any $S \subset [n]$ with $|S| = n - (k+1)$.

4. {$w \in \mathfrak{S}_n \mid \mathrm{des}(w) = k, \mathrm{cover}(w) = 1$} = $\binom{n}{k+1}$.

**Proposition 6.4** For any $1 < k < n$, we have

1. {$w \in \mathfrak{S}_n \mid \mathrm{exc}(w) = 1, \mathrm{des}(w) = k$} = $\binom{n+1}{2k}$.

2. {$w \in \mathfrak{S}_n \mid \mathrm{des}(w) = 1, \# \mathrm{Expose}(w) = n - 2k \text{ or } n + 1 - 2k$} = 1

3. {$w \in \mathfrak{S}_n \mid \mathrm{des}(w) = 1, \# \mathrm{Expose}(w) = n - 2k \text{ or } n + 1 - 2k$} $\subset \{w \in \mathfrak{S}_n \mid \mathrm{cover}(w) = k\}$.

4. {$w \in \mathfrak{S}_n \mid \mathrm{des}(w) = 1, \mathrm{cover}(w) = k$} = $\binom{n}{2k} + \binom{n}{2k-1} = \binom{n+1}{2k}$.

Acknowledgements

I thank my advisor Richard Stanley for introducing me to the problem and giving me help and encourage-
ment, Ira Gessel, Yan Zhang and Steven Sam for helpful communication.

References

[1] E. De Negri, T. Hibi, *Gorenstein algebras of Veronese type*, J. Algebra, 193 (1997) 629–639.

[2] D. Foata and G. Han, *Fix-Mahonian calculus III; a quadruple distribution*, Monatsh Math 154. 177–197 (2008).

[3] M. Katzmann, *The Hilbert series of algebras of Veronese type*, to appear in Communications in Algebra.

[4] N. Li, *Ehrhart h*-vectors of hypersimplices, Discrete and Computational Geometry 38 no. 48 (2012) 847–878.

[5] T. Lam, A. Postnikov, *Alcoved polytopes I*, Discrete and Computational Geometry 38 no. 3 (2007) 453–478.

[6] R. Stanley, *Eulerian partitions of a unit hypercube*, in Higher Combinatorics (M. Aigner, ed), Reidel, Dordrecht/Boston, 1977, p.49.

[7] R. Stanley, *Decompositions of rational convex polytopes*, Annals of Discrete Math, volume 6 (1980), 333-342.

[8] R. Stanley, *Combinatorics and commutative algebra, second ed.*, Progress in Mathematics, vol. 41, Birkhäuser Boston Inc., Boston, MA, 1996.

[9] R. Stanley, *Enumerative combinatorics, Volume 1*, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Cambridge, 1997.

[10] B. Sturmfels, *Gröbner bases and convex polytopes*, University Lecture Series, 8. American Mathematical Society, Providence, RI, 1996.