PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 81(95) (2007), 85–93 DOI 102298/PIM0795085J

EXTENDABLE SHELLING, SIMPLICIAL AND TORIC h-VECTOR OF SOME POLYTOPES

Duško Jojić

Abstract. We show that the stellar subdivisions of a simplex are extendably shellable. These polytopes appear as the facets of the dual of a hypersimplex. Using this fact, we calculate the simplicial and toric h-vector of the dual of a hypersimplex. Finally, we calculate the contribution of each shelling component to the toric h-vector.

1. Introduction

A polytopal (polyhedral) complex is a finite set C of polytopes (including ∅ ∈ C) satisfying:

(i) if P ∈ C and Q is a face of P, then Q ∈ C;

(ii) For all P, Q ∈ C, P ∩ Q is a (possible empty) face of both P and Q. For the definitions and properties of polytopes, see [10]. A simplicial complex is a special case of polytopal complex, the case when every polytope is a simplex. In this paper we consider only pure complexes C, that is, complexes which satisfy the condition that all the maximal faces with respect to inclusion, called the facets of C, have the same dimension, called the dimension of C.

An example of a pure polytopal complex is the boundary complex C(∂P) of a polytope P; the set of the faces of P except for the polytope itself.

A shelling of a polytopal complex C is a linear ordering F_{1}, F_{2}, …, F_{k} of its facets which is arbitrary for dim C = 0 (all F_{i} are points), and for dim C > 0 has to satisfy the following conditions (see [4] or Section 8 in [10]):

(i) The boundary complex C(∂F_{1}) of the first facet has a shelling.

(ii) For every i > 1, the intersection of F_{i} with the previous facets is a beginning part of a shelling of the boundary complex C(∂F_{i}), that is:

F_{i} ∩ (⋃_{j<i} F_{j}) = G_{1} ∪ G_{2} ∪ ⋯ ∪ G_{l}

for some shelling G_{1}, G_{2}, …, G_{l}, …, G_{m} of C(∂F_{i}).

2000 Mathematics Subject Classification: Primary 52B22; Secondary 52B05.

Key words and phrases: extendable shellability, hypersimplex, toric h-vector.

For polytopal complexes, the condition (i) is pleonastic, because the boundary of any polytope is shellable, see [4]. Further, for simplicial complexes, the condition (ii) can be simplified:

For every i < j ⩽ k there exist some l < j and a vertex v of F_{j} such that

(1)  F_{i} ∩ F_{j} ⊂ F_{l} ∩ F_{j} = F_{j} ∖ {v}.

A polytopal (simplicial) complex C is extendably shellable if every partial shelling can be extended to a complete shelling of C. This concept is essential for the algorithmic use of shellings, but we know very few about extendable shellability. Ziegler showed in [9] that the boundaries of “almost all” 4-polytopes are not extendably shellable.

For a d-dimensional polytopal (simplicial) complex C, we denote the number of i-dimensional faces of C by f_{i}, and f(C) = (f_{0}, f_{1}, …, f_{d}) is called the f -vector. A generating polynomial for the f-vector is the f -polynomial:

f(C, x) = x^{d+1} + f_{0}x^{d} + f_{1}x^{d−1} + ⋯ + f_{d−1}x + f_{d}.

A new invariant, the h -vector h(C) = (h_{0}, h_{1}, …, h_{d}, h_{d+1}) is defined to be the coefficients of f(C, x − 1):

(2)  f(C, x − 1) = h_{0}x^{d+1} + h_{1}x^{d} + ⋯ + h_{d}x + h_{d+1} = h(C, x).

The h-vector of a shellable simplicial complex C has the following combinatorial interpretation. For a fixed shelling F_{1}, F_{2}, …, F_{k} of C, we define the restriction R_{j} of the facet F_{j}:

R_{j} = {v ∈ V (F_{j}) : F_{j} ∖ {v} ⊂ F_{i} for some 1 ⩽ i < j},

that is, R_{j} is a minimal new face at the j-th step in the given shelling.

The type of F_{j} in the given shelling is the cardinality of R_{j}, i.e., type(F_{j}) = |R_{j}|. Now, we have that

h_{k}(C) = |{j : type(F_{j}) = k}|.

This interpretation of the h-vector was of great significance in the proof of the upper-bound theorem and in the characterization of f-vectors of simplicial polytopes, see [10].

The entries of the h-vector of a simplicial polytope are Betti numbers of the associated toric variety. This can be generalized to nonsimplicial polytopes, to define the toric h-vector, but we do not have combinatorial interpretation for the entries of this vector.

In this paper, we use the combinatorial formula for the toric h-vector of Eulerian poset given by Stanley [8]. To a graded poset P we associate two polynomials, f(P, t) and g(P, t) recursively:

(1) For the Boolean lattice B_{1}, the only graded poset of rank 1, we have f(B_{1}, t) = g(B_{1}, t) = 1.

(2) If rank(P) = n + 1 > 0, then f(P, t) has the degree n, say f(P, t) = h_{0}^{T} + h_{1}^{T} t + ⋯ + h_{n−1}^{T}t^{n−1} + h_{n}^{T} t^{n}, and we define g(P, t) = h_{0}^{T} + (h_{1}^{T} − h_{0}^{T})t + ⋯ + (h_{[n/2]}^{T} − h_{[n/2]−1}^{T})t^{[n/2]}.

EXTENDABLE SHELLING, SIMPLICIAL AND TORIC h-VECTOR 87

(3) If rank(P) = n + 1 > 0 we define

(3)  f(P, t) = ∑_{x∈P, x<ˆ1_{P}} g ([ˆ0_{P} , x], t) (t − 1)^{n−r(x)}.

The toric h-vector h^{T} (P) = (h_{0}^{T} , h_{1}^{T} , …, h_{n}^{T}) of an Eulerian poset P is defined as the vector of coefficients of the polynomial f(P, t).

For all simplicial Eulerian posets the toric h-vector coincides with the usual h-vector, defined with relation (2). Further, for the entries of the toric h-vector of any Eulerian poset of rank n + 1 holds h_{i}^{T} = h_{n−i}^{T}.

A poset P is quasisimplicial if for any coatom c of P, the interval [ˆ0, c] is simplicial, that is, for any corank 2 element x of P, the interval [ˆ0, x] is a Boolean algebra. From the formulae (3) and the fact that for all Boolean lattices B_{m} the equality g(B_{m}, t) = 1 holds, we can obtain that for a quasisimplicial poset P whose h-vector is h(P) = (h_{0}, h_{1}, …, h_{n}) the toric h-vector of P is

(4)  h_{i}^{T} = \begin{cases}h_{i} & for i ⩽ [n/2], \\ h_{n−i} & for i > [n/2]. \end{cases}

2. Polytopes T_{k}^{n} are extendable shellable

The stellar subdivision of a polytope P in a face F (see [6] for more details) is a new polytope conv(P ∪ x^{F}), where x^{F} is a point of the form y^{F} − ε(y^{P} − y^{F}), where y^{P} is in the interior of P, y^{F} is in the relative interior of F, and ε is small enough. Let T_{k}^{n} denotes a polytope obtained as a stellar subdivision of n-simplex Δ_{n} in a k-face S. Obviously, T_{k}^{n} is simplicial and in [2] we can find that

(5)  ∂T_{k}^{n} = (Δ_{n} ∖ S) ∪ (∂S ∗ ∂lk_{Δ_{n}}S ∗ {x^{S}}) .

Remark 1. Let us denote the vertices of S with r_{1}, r_{2}, …, r_{k+1}; the vertices of Δ_{n} ∖ S denote with c_{1}, c_{2}, …, c_{n−k}, and let c_{n−k+1} denotes the new vertex x^{S}. Now, we have that the set of the vertices of T_{k}^{n} is

V (T_{k}^{n}) = {r_{1}, r_{2}, …, r_{k+1}} ∪ {c_{1}, c_{2}, …, c_{n−k}, c_{n−k+1}}.

From the relation (5), we conclude that all facets of T_{k}^{n} are just (n − 1)-simplices F_{i,j} = conv(V (T_{k}^{n})∖{r_{i}, c_{j}}), for all i = 1, 2, …, k +1; j = 1, 2, …, n−k, n−k +1. Therefore, if we label rows and columns of a (k + 1) × (n − k + 1) rectangle R_{(k+1)×(n−k+1)} with vertices r_{1}, r_{2}, …, r_{k+1} and c_{1}, c_{2}, …, c_{n−k}, c_{n−k+1} of T_{k}^{n}, then facets of T_{k}^{n} correspond with (k + 1)(n − k + 1) squares of R_{(k+1)×(n−k+1)}.

Now, with an appropriate labelling of the vertices, we can prove that the following complexes are combinatorially equivalent: ∂T_{k}^{n} ≅ ∂(Δ_{k} × Δ_{n−k})^{∗} ≅ ∂Λ_{k}^{n+1} (here Λ_{k}^{n+1} is a simplicial n-disk, obtained as the union of k +1 facets of an (n+1)- simplex).

Note that the facets F_{i,j} and F_{p,q} of T_{k}^{n} share a common (n − 2)-simplex if and only if i = p or j = q (corresponding squares are in the same row or column of R_{(k+1)×(n−k+1)}). Now, it is easy to verify that the lexicographical order of the facets of T_{k}^{n}

(6)  F_{i,j} < F_{p,q} ⇔ i < p or i = p, j < q

is a shelling order. In this order we have that type(F_{i,j}) = i + j − 2, so we can conclude that for 0 ⩽ k ⩽ n − k the h-vector of the polytopes T_{k}^{n} is h(T_{k}^{n}) = (1, 2, …, k, k + 1, …, k + 1, k, …, 1).

Theorem 2. Polytopes T_{k}^{n} are extendably shellable.

Proof. Let F be a subset of the facets of T_{k}^{n}, which we can identify with the squares in the rectangle R_{(k+1)×(n−k+1)}. For all i = 1, 2, …, k + 1 we let F_{i} = {j ∈ [n − k + 1] : F_{i,j} ∈ F}; i.e., F_{i} is the set of the squares from F contained in the i-th row of R_{(k+1)×(n−k+1)}. We will prove that the following statements are all equivalent:

(a) there exists a shelling order for the union of the facets contained in F.

(b) the sets F_{i} form a chain: for all i, j we have that F_{i} ⊆ F_{j} or F_{j} ⊆ F_{i}.

(c) there exists a shelling of T_{k}^{n} with the facets from F at the beginning.

(a) ⇒ (b). Assume that for some i, i′ there exists j such that j ∈ F_{i} and j ∉ F_{i′}. Now, from the shellability of F, for all j′ ∈ F_{i′}, the intersection F_{i,j} ∩F_{i′,j′} is contained in an (n − 2)-simplex, which is the intersection of F_{i,j} or F_{i′,j′} with a facet from F, see (1). The only facets of T_{k}^{n} with the above properties are F_{i,j′} and F_{i′,j}. As we assumed that F_{i′,j} ∉ F, then shellability of F implies that F_{i,j′} ∈ F, and therefore F_{i} ⊇ F′_{i}.

(b) ⇒ (c). We may assume that F_{1} ⊇ F_{2} ⊇ … ⊇ F_{k+1} (because we can relabel the vertices of S). We define the following linear order for the facets of T_{k}^{n}:

(7)  F_{i,j} < F_{k,l} ⇔ either j ∈ F_{i}, l ∉ F_{k} or i < k ∨ i = k, j < l.

If F_{a,b} precedes to F_{c,d} in this order we consider the two possibilities:

1^{∘} a ⩽ c, when b ∉ F_{a}, d ∉ F_{c} or b ∈ F_{a}, d ∈ F_{c} or b ∈ F_{a}, d ∉ F_{c}, and then

F_{a,b} ∩ F_{c,d} ⊆ F_{a,d} ∩ F_{c,d} = F_{c,d} ∖ {r_{a}};

2^{∘} c < a, when b ∈ F_{a}, d ∉ F_{c}, and then F_{a,b}∩F_{c,d} ⊆ F_{c,b}∩F_{c,d} = F_{c,d}∖{c_{b}}.

Note that F_{a,d} (and F_{c,b} in the second case) precedes to F_{c,d} in the given order. Therefore, a shelling order for the facets of T_{k}^{n} is defined by (7).

Finally, the implication (c) ⇒ (a) is obvious. □

It is shown in [5] that the cross polytope Cn^{Δ} (the convex hull of the standard basis vectors in ℝ^{n} and their negatives), is not extendably shellable in dimension 12 or higher. The cross polytope can be obtained as the dual of the product of segments, or by successive stellar subdivisions of a simplex, so we cannot generalize Theorem 2 in this way.

3. Simplicial and toric h-vector of Δ_{n−1}^{∗}(k)

The hypersimplex Δ_{n−1}(k) is a polytope in ℝ^{n} obtained as the intersection of the n-cube C_{n} = [0, 1]^{n} with the hyperplane H_{k} = {x ∈ ℝ^{n} : ∑_{i=1}^{n} x_{i} = k}. In particular, Δ_{n−1}(1) and Δ_{n−1}(n − 1) are (n − 1)-simplices. As the polytopes Δ_{n−1}(k) and Δ_{n−1}(n − k) are isomorphic, we can assume that 0 ⩽ k ⩽ n − k. The face lattice L(Δ_{n−1}(k)) of a hypersimplex is described with the following

Lemma 3. Let

\begin{aligned}L_{n−1}(k) = \{(A, B) : A ⊂ B ⊆ [n]; |A| & < k; |B| > k\} \\ ∪\{(A, A) : A ⊆ [n]; |A| & = k\} ∪ \{ˆ0\}. \end{aligned}

If we define an order on L_{n−1}(k) with (A, B) ⩽ (C, D) ⇔ A ⊇ C, B ⊆ D, then L(Δ_{n−1}(k)) ≅ L_{n−1}(k).

Proof. Note that H_{k} does not intersect the edges of C_{n} in their relative interior. Therefore, the only vertices of Δ_{n−1}(k) are vertices of C_{n} contained in H_{k}. The correspondence

A = \{a_{1}, a_{2}, …, a_{k}\} ⊆ [n], (A, A) ↔ T_{A} = (t_{1}, t_{2}, …, t_{n}), t_{i} = \begin{cases}1, & i ∈ A; \\ 0, & i ∉ A \end{cases}

gives us a bijection between the atoms of L_{n−1}(k) and the vertices of Δ_{n−1}(k). For any pair (A, B) of the subsets of [n], such that

(8)  A ⊂ B ⊆ [n]; |A| ⩽ k − 1; |B| ⩾ k + 1,

the linear functional x ↦ ∑_{i∈A} x_{i}−∑_{j∉B} x_{j} reaches the maximum on the Δ_{n−1}(k) at the (|B| − |A| − 1)-dimensional face

S_{(A,B)} = {x ∈ C_{n} : ∑_{i=1}^{n} x_{i} = k; ∀i ∈ A, x_{i} = 1; ∀j ∉ B, x_{j} = 0}.

So, we establish a bijection between all of pairs (A, B) for which the relation (8) holds and all (|B| − |A| − 1)-faces of Δ_{n−1}(k). Also, it is easy to see that the correspondence (A, B) ↦ S_{(A,B)} defines a poset isomorphism between L_{n−1}(k) and the face lattice L(Δ_{n−1}(k)). □

Note that the face lattice of the dual polytope Δ_{n−1}^{∗}(k) can be obtained by applying the E_{t}-construction on the Boolean lattice B_{n}, see in [7].

Remark 4. For a vertex T_{A} of Δ_{n−1}(k), denote by F_{A} its corresponding facet in Δ_{n−1}^{∗}(k). For 1 < k < n, note that Δ_{n−1}(k) has 2n facets R_{i} and C_{j}:

R_{i} = {x ∈ Δ_{n−1}(k) : x_{i} = 1} = S_{({i},[n])} = conv({T_{A} : i ∈ A}),
C_{j} = {x ∈ Δ_{n−1}(k) : x_{j} = 0} = S_{(∅,[n]∖{j})} = conv({T_{A} : j ∉ A}).

Therefore, Δ_{n−1}^{∗}(k) has 2n vertices: V (Δ_{n−1}^{∗}(k)) = {r_{1}, …, r_{n}, c_{1}, … c_{n}}. The vertex T_{A} in Δ_{n−1}(k) is contained in the facets R_{i}, for i ∈ A and C_{j}, for j ∉ A. Therefore, the set of the vertices of F_{A} is V (F_{A}) = {r_{i} : i ∈ A} ∪ {c_{j} : j ∉ A}.

An edge E = S_{(A∖{i_{0}},A∪{j_{0}})} of Δ_{n−1}(k), which contains T_{A}, is contained in the facets R_{i}, for i ∈ A ∖ {i_{0}} and C_{j}, for j ∈ A^{c} ∖ {j_{0}}. So, we have that the maximal face of F_{A}, which corresponds to E, is an (n − 3)-simplex G_{r_{i_{0}} ,c_{j_{0}}} (A) = conv(V (F_{A}) ∖ {r_{i_{0}}, c_{j_{0}}}).

For A = {a_{1}, a_{2}, …, a_{k}} ⊂ [n], we denote the i-th row of a k ×(n−k) rectangle with r_{a_{k+1−i}}. If A^{c} = {b_{1}, b_{2}, …, b_{n−k}}, then the j-th columns we denote with c_{b_{j}}. Now, from Remark 1 it follows that all of the facets of Δ_{n−1}^{∗}(k) are combinatorially equivalent with T_{k−1}^{n−2}.

Note that G_{r_{a},c_{b}}(A) and G_{r_{b},c_{a}}(A∖{a}∪{b}) denote the same faces of Δ_{n−1}^{∗}(k) (the common facets of F_{A} and F_{A∖{a}∪{b}}). So, with

G_{r_{a},c_{b}}(A), for A ⊂ [n], |A| = k; a < b, a ∈ A, b ∉ A,

we list all of (n − 3)-faces of Δ_{n−1}^{∗}(k).

Now, we consider a lexicographic order of the facets of Δ_{n−1}^{∗}(k):

(9)  F_{A} <_{L} F_{B} ⇔ A <_{L} B ⇔ min(A △ B) ∈ A.

If we denote with Γ_{A} the intersection of the facet F_{A} with the previous facets in this order, we can prove that

Γ_{A} = F_{A} ∩ ( ⋃_{F_{A′} <_{L}F_{A}} F_{A′}) = ⋃_{a∈A, b∈[n]∖A, b<a} G_{r_{a},c_{b}}(A).

Now, we use well known bijection between k-subsets of an n-set (facets of Δ_{n−1}^{∗}(k)), and all shortest paths from lower left-hand corner, and ending at the upper righthand corner of a k × (n − k) rectangle. The squares above this path correspond with facets of F_{A} contained in Γ_{A}.

From Theorem 2, it follows that there exists a shelling for facets from Γ_{A}, and this shelling can be extended to the shelling of the whole F_{A}, and therefore <_{L} is a shelling order for the facets of Δ_{n−1}^{∗}(k).

Further, motivated by (6), we can define the linear order of the (n − 3)-faces of Δ_{n−1}^{∗}(k):

G_{r_{a},c_{b}}(A) < G_{r_{k},c_{l}}(A′) ⇔ \begin{cases}A <_{L} A′, & or \\ A = A′, r_{a} > r_{k}, & or \\ A = A′, r_{a} = r_{k} and c_{b} < c_{l}. \end{cases}

It is easy to prove that this is a shelling order for (n − 3)-skeleton of Δ_{n−1}^{∗}(k). Also, we can note in the above list, that from a facet F_{A} we take just the facets which does not appear in Γ_{A}, i.e., facets whose corresponding squares are bellow corresponding path. When the simplex G_{r_{a},c_{b}}(A) corresponds with the square (i, j) in a k × (n − k) rectangle, then its type in described shelling is i + j − 2. Therefore, the square (i, j) below the corresponding path, contributes the one to i+j −2 entry of h-vector of Δ_{n−1}^{∗(n−3)}(k).

If we define a k × (n − k) matrix A_{k,n−k} with a_{i,j} = number of paths in R_{k×(n−k)}, in which the square (i, j) are below, then we have that

h_{k}(Δ_{n−1}^{∗(n−3)}(k)) = ∑_{i+j=k+2} a_{i,j}.

By considering the possibilities for the first step in a such path, it is easy to note that the matrices A_{k,n−k} satisfy the following recursive relations:

(10)  A_{k,n−k} = [0 0 ⋮ 0 A_{k,n−k−1}] + [\begin{matrix}& A_{k−1,n−k} \\ \binom{n−1}{k−1} & \binom{n−1}{k−1} & ⋯ & \binom{n−1}{k−1} \end{matrix}]

Theorem 5. For all n ∈ ℕ and 0 ⩽ k ⩽ n − k it holds:

(11)  h(Δ_{n−1}^{∗}(k)) = (  \binom{n}{0} ; \binom{n}{0} + \binom{n}{1} ; ⋮ ; \binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{k−1} ; ⋮ ; \binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{k−1} ; ⋮ ; \binom{n}{0}) − \binom{n}{k} (0 0 ⋮ 0 1 1 ⋮ 1 0) ^{\} \begin{matrix}n−k \\ zeros \end{matrix}}

Proof. From Euler–Poincaré formula we know that the last entry of h-vector is always equal 1. The above combinatorial interpretation for the h-vector of the (n − 3)-skeleton of Δ_{n−1}^{∗}(k) and relation (10) gives us that:

h^{(n−3)}(Δ_{n−1}^{∗}(k)) = (\begin{matrix}0 \\ h^{(n−4)}(Δ_{n−2}^{∗}(k)) \end{matrix})+(\begin{matrix}h^{(n−4)}(Δ_{n−2}^{∗}(k − 1)) \\ 0 \end{matrix})+( 0 ; ⋮ ; 0 ; \binom{n−1}{k−1} ; ⋮ ; \binom{n−1}{k−1}) ^{\} \begin{matrix}k−1 \\ zeros \end{matrix}}

Let us to denote with h̃(P) “the reduced” h vector of a polytope P, i.e., h(P) = (h̃(P), 1). Now we use Stanley’s trick to compute the h-vector of Δ_{n−1}^{∗}(k). From the above we obtain the following recursive relations

\begin{aligned}h̃(Δ_{n−1}^{∗}(k)) = (0, h̃(Δ_{n−2}^{∗}(k))) & + (h̃(Δ_{n−2}^{∗}(k − 1)), 0) \\ & + ( \underbrace{0, …, 0}_{k−1}, \binom{n−1}{k−1}, 0, …, 0, 1 − \binom{n−1}{k−1}). \end{aligned}

Note that \binom{n−1}{k−1} − 1 is the last entry of h^{(n−4)}(Δ_{n−2}^{∗}(k − 1)). The formulae (11) will follow from the above relation and beginning conditions; Δ_{2}^{∗}(1) i Δ_{2}^{∗}(2) are 2-simplexes. □

Now, we consider the toric h-vector of Δ_{n−1}^{∗}(k). The polytopes Δ_{n−1}^{∗}(k) are quasisimplicial, and from the formulae (4), for 0 ⩽ k ⩽ n − k we have that

h^{T} (Δ_{n−1}^{∗}(k)) = (\binom{n}{0}, \binom{n}{0} + \binom{n}{1}, …, \binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{k−1},
…, \binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{k−1}, …, \binom{n}{0} + \binom{n}{1}, \binom{n}{0}).

Bayer showed in [1] how the shelling of the ordinary polytope could be used to compute the toric h-vector. Here, we are able to compute the toric h-vector of Δ_{n−1}^{∗}(k) from the shelling order described in (9). For this we need the following theorem, see [3].

Theorem 6. For a d-disk Γ whose h-vector is h(Γ) = (h_{0}, h_{1}, …, h_{d}, 0) and its boundary (d − 1)-sphere ∂Γ the following equality holds

h_{i}(∂Γ) = h_{0} + h_{1} + ⋯ + h_{i} − h_{d+1−i} − ⋯ − h_{d+1}, for 0 < i ⩽ [d/2].

With h_{A}^{T}(t) we denote the contributions to h(Δ_{n−1}^{∗}(k), t) of the faces that appear for the first time when we add facet F_{A}:

h_{A}^{T}(t) = ∑ ; G⊆F_{A}, G∉⋃_{B<A} F_{B} g(G, t)(t − 1)^{n−dim G}.

Theorem 7. For 1 ⩽ a_{1} < a_{2} < ⋯ < a_{k} ⩽ n and A = {a_{1}, a_{2}, …, a_{k}} we have h_{A}^{T}(t) = t^{n−k−1} ∑_{i=1}^{k} t^{2i−a_{i}}.

Proof. If we denote with Λ_{A} the intersection of the facet F_{A} with the facets that came after F_{A} in the shelling order given in the relation (9), new faces are exactly those from Λ_{A} ∖ ∂Λ_{A}. Therefore, from the definition of h_{A}^{T} we obtain:

h_{A}^{T} = ∑_{F ∈Λ_{A}} g(F, t)(t − 1)^{n−1−dim F} − ∑_{F ∈∂Λ_{A}} g(F, t)(t − 1)^{n−1−dim F} + g(F_{A}, t).

The face posets of Λ_{A} and ∂Λ_{A} are simplicial, and therefore we can compute their contribution to the h_{A}^{T} from the usual (simplicial) h-vector of Λ and ∂Λ. So, we have

(12)  h_{A}^{T} = (t − 1)h(Λ_{A}, t) − (t − 1)^{2}h(∂Λ_{A}, t) + t^{k−1} + t^{k−2} + ⋯ + t + 1.

In a shelling order for Λ_{A}, the reverse order of the one given in (6), the contribution of the squares from the (k +1−i)-th row (the row denoted with r_{a_{i}}) to the h-vector of Λ_{A} is

h_{a_{i}} = (\overbrace{0, 0, …, 0}^{i−1}, \overbrace{1, 1, …, 1}^{n−k−a_{i}+i}, \overbrace{0, …, 0}^{k−2i+a_{i}}).

If i − 1 ⩽ k − 2i + a_{i}, from Theorem 6, we know that the contribution of a_{i} to the h-vector of ∂Λ_{A} is

(\overbrace{0, 0, …, 0}^{i−1}, 1, 2, …, r, r …, r, r, …, 2, 1, \overbrace{0, 0, …, 0}^{i−1})

When we put this in (12), we obtain that the contribution of the a_{i} to h_{A}^{T} is exactly t^{n+2i−k−a_{i}−1}.

A similar calculation goes for the case i − 1 > k − 2i + a_{i}, and the theorem follows. □

References

[1] M. Bayer, Shelling and the h-vector of the (extra)ordinary polytope, In: Jacob Eli Goodman et al. (eds.), Combinatorial and Computational Geometry, Cambridge University Press, 2005, pp. 97–120.

[2] M. Bayer, L. Billera, Counting faces and chains in polytopes and posets, In: C. Greene (ed.): Combinatorics and Algebra, Contemporary Math. 34, American Mathematical Society, 1984, 207–252.

[3] L. Billera , A. Björner, Face numbers of polytopes and complexes, In: J. E. Goodman, J. O’Rourke (eds.), CRC Handbook on Discrete and Computational Geometry, CRC Press, Boca Ration (Florida), 1997, 291–310.

[4] M. Bruggeser, P. Mani, Shellable decompositions of cells and spheres, Math. Scand. 29 (1971), 197–205.

[5] T. H. Huntington, Counterexamples in Discrete Geometry, PhD thesis, University of California, Berkeley, 2004.

[6] M. Henk, J. Richter-Gebert, and G. M. Ziegler, Basic properties of convex polytopes, In: J. E. Goodman, J. O’Rourke (eds.), CRC Handbook on Discrete and Computational Geometry, CRC Press, Boca Ration (Florida), 1997, 243–270.

[7] A. Paffenholz, G. M. Ziegler, The E_{t}-construction for lattices, spheres and polytopes, Discrete Comput. Geom. 32:4 (2004), 601–621.

[8] R. P. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth and Brooks/Cole, Pacific Grove, 1986.

[9] G. M. Ziegler, Shelling polyhedral 3-balls and 4-polytopes, Discrete Comput. Geom. 19:2 (1998), 159–174.

[10] G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995.

Prirodno-matematički fakultet 78000 Banja Luka Bosnia and Herzegovina

ducci68@blic.net