FLAG VECTORS OF MULTIPLICIAL POLYTOPES

MARGARET M. BAYER

Abstract. Bisztriczky introduced the multiplex as a generalization of the simplex. A polytope is multiplicial if all its faces are multiplexes. In this paper it is proved that the flag vectors of multiplicial polytopes depend only on their face vectors. A special class of multiplicial polytopes, also discovered by Bisztriczky, is comprised of the ordinary polytopes. These are a natural generalization of the cyclic polytopes. The flag vectors of ordinary polytopes are determined. This is used to give a surprisingly simple formula for the h-vector of the ordinary d-polytope with n + 1 vertices and characteristic k: h_{i} = \binom{k−d+i}{i} + (n − k)\binom{k−d+i−1}{i−1}, for i ≤ d/2. In addition, a construction is given for 4-dimensional multiplicial polytopes having two-thirds of their vertices on a single facet, answering a question of Bisztriczky.

1. Introduction

Convex polytopes arise in many areas of mathematics and its applications. Of great interest are their combinatorial aspects, and, in particular, the numbers of faces of convex polytopes. In this area, the biggest result was the characterization of the f-vector (the sequence of face numbers) of simplicial convex polytopes in 1980 by Billera and Lee [4] and Stanley [11]. Simplicial polytopes are those for which every proper face is a simplex. For nonsimplicial polytopes we have seen no such success. Contributing to our failure is the lack of constructions of polytopes with sufficiently varied facial structures.

In [5] Bisztriczky introduced the multiplex as a generalization of the simplex. There is a d-dimensional multiplex with v vertices for each v ≥ d + 1. Multiplexes share many of the nice properties of simplices; in particular they are self-dual and every face and every quotient of a multiplex is a multiplex. It is natural, therefore, to study the combinatorics of multiplicial polytopes, polytopes whose faces are multiplexes. All polygons are multiplexes, so all 3-dimensional polytopes are multiplicial. The story begins, therefore, in dimension 4. This is also where the open problems on face numbers of general polytopes begin.

In [6] Bisztriczky introduced a fascinating class of multiplicial polytopes, called ordinary polytopes. Multiplexes and ordinary polytopes have been further studied in [7] and [2]. This paper continues the study of f-vectors and flag vectors of multiplicial polytopes. In addition, we give a construction of multiplicial 4-polytopes with large facets.

We turn now to the necessary definitions and background theorems.

Research at MSRI is supported in part by NSF grant DMS-9810361. This research was also supported by a University of Kansas General Research Fund Grant.

Definition 1.1 ([5]). A d-dimensional multiplex is a polytope with an ordered list of vertices, x_{0}, x_{1}, …, x_{n}, with facets F_{0}, F_{1}, …, F_{n} given by

F_{i} = conv{x_{i−d+1}, x_{i−d+2}, …, x_{i−1}, x_{i+1}, x_{i+2}, …, x_{i+d−1}},

with the conventions that x_{i} = x_{0} if i < 0, and x_{i} = x_{n} if i > n.

Theorem 1.1 ([5]).

(1) For every d and n with n ≥ d ≥ 2, there exists a d-dimensional multiplex M^{d,n} with n + 1 vertices.

(2) Every multiplex is self-dual.

(3) Every face and every quotient of a multiplex is a multiplex.

(4) The number of i-dimensional faces of M^{d,n} is \binom{d+1}{i+1} + (n − d)\binom{d−1}{i}.

By definition the combinatorial type of M^{d,n} is completely determined by d and n. If d = n, of course, the multiplex is the simplex.

In the study of nonsimplicial polytopes, the f-vector does not carry enough combinatorial information. We are interested in incidences of faces as well. A chain of faces, ∅ ⊂ F_{1} ⊂ F_{2} ⊂ ⋯ ⊂ F_{r} ⊂ P is an S-flag if S = {dim F_{1}, dim F_{2}, …, dim F_{r}}. The number of S-flags of a polytope P is written f_{S}(P), and the length 2^{d} vector (f_{S}(P))_{S⊆{0,1,...,d−1}} is the flag vector of P. The flag vector restricts to the f-vector by considering only the singleton sets S. The flag vector of the multiplex is a familiar object.

Theorem 1.2 ([2]). The multiplex M^{d,n} has the same flag vector as the (d − 2)-fold pyramid over the (n − d + 3)-gon. The common flag vector is given by

(1)  f_{S} = \binom{d + 1}{s_{1} + 1, s_{2} − s_{1}, …, s_{r} − s_{r−1}, d − s_{r}}

× [1 + \frac{n − d}{(d + 1)d(d − 1)} ∑_{j=1}^{r}(s_{j} + 1)(s_{j+1} − s_{j})(s_{j+1} − 1)] ,

where S = {s_{1}, s_{2}, …, s_{r}}, s_{1} < s_{2} < ⋯ < s_{r}, and s_{r+1} = d.

2. Results for general multiplicial polytopes

There are two natural classes of polytopes that could be called “multiplicial”. One might call a polytope multiplicial if all of its proper faces are multiplexes. However, a multiplex is really a polytope endowed with a special ordering of its vertices. It is natural to take the ordering into account when defining multiplicial, and Bisztriczky indeed does this. We will use both concepts in this paper.

Definition 2.1. A polytope P is (weakly) multiplicial if and only if every proper face of P is a multiplex.

Definition 2.2. A polytope P is order-multiplicial if and only if for some ordering v_{0}, v_{1}, …, v_{n} of the vertices of P, every proper face of P is a multiplex with the induced ordering of its vertices.

Let P^{d} be the set of d-polytopes in R^{d}. Let f_{S} : P^{d} → N be the function that gives the number of S-flags of P for a d-polytope P. In particular f_{i} is the function that gives the number of i-faces of P. Write f_{S}^{⋄} for the restriction of the S-flag function to multiplicial polytopes. For a multiplicial polytope, the flag vector of each proper face depends only on its number of vertices. This leads to the following result.

Theorem 2.1. Fix d ≥ 2, and let S be a nonempty subset of {0, 1, …, d − 1} with maximum element t. There exist rational numbers a and b such that f_{S}^{⋄} = af_{t}^{⋄} +bf_{0,t}^{⋄}.

For S = {s_{1}, s_{2}, …, s_{r}}, with s_{1} < s_{2} < ⋯ < s_{r} = t,

a = \binom{s_{r} + 1}{s_{1} + 1, s_{2} − s_{1}, …, s_{r} − s_{r−1}}

× [1 − \frac{1}{s_{r}(s_{r} − 1)} ∑_{j=1}^{r−1}(s_{j} + 1)(s_{j+1} − s_{j})(s_{j+1} − 1)] ,

and

b = \binom{s_{r} + 1}{s_{1} + 1, s_{2} − s_{1}, …, s_{r} − s_{r−1}}

× [\frac{1}{(s_{r} + 1)s_{r}(s_{r} − 1)} ∑_{j=1}^{r−1}(s_{j} + 1)(s_{j+1} − s_{j})(s_{j+1} − 1)] .

Proof. We first observe that the statement holds trivially for |S| = 1. For |S| ≥ 2, we use the formula for the flag vectors of multiplexes (see Theorem 1.2). Suppose S = {s_{1}, s_{2}, …, s_{r}}, with s_{1} < s_{2} < ⋯ < s_{r}, and write s_{r+1} = d. For the d-multiplex M^{d,n} with n + 1 vertices, f_{S}(M^{d,n}) = a_{S,d} + b_{S,d}(n + 1) = a_{S,d} + b_{S,d}f_{0}(M^{d,n}), where

a_{S,d} = \binom{d + 1}{s_{1} + 1, s_{2} − s_{1}, …, s_{r} − s_{r−1}, d − s_{r}}

× [1 − \frac{1}{d(d − 1)} ∑_{j=1}^{r}(s_{j} + 1)(s_{j+1} − s_{j})(s_{j+1} − 1)] ,

and

b_{S,d} = \binom{d + 1}{s_{1} + 1, s_{2} − s_{1}, …, s_{r} − s_{r−1}, d − s_{r}}

× [\frac{1}{(d + 1)d(d − 1)} ∑_{j=1}^{r}(s_{j} + 1)(s_{j+1} − s_{j})(s_{j+1} − 1)] .

Now fix d ≥ 2, and let S be a subset of {0, 1, …, d − 1} with |S| ≥ 2 and maximum element t. Let P be a multiplicial d-polytope. Every t-face F of P is a t-dimensional multiplex, so f_{S\{t}}(F) = a_{S\{t},t} + b_{S\{t},t}f_{0}(F). Then

f_{S}(P) = ∑_{F t-face of P} f_{S\{t}}(F)
= ∑_{F t-face of P} a_{S\{t},t} + b_{S\{t},t}f_{0}(F)
= a_{S\{t},t}f_{t}(P) + b_{S\{t},t}f_{0,t}(P).
□

Theorem 2.2. For each S ⊆ {0, 1, …, d−1}, the function f_{S}^{⋄} is a linear combination of the constant function f_{∅}^{⋄}(P) = 1 and the face number functions f_{i}^{⋄}, 0 ≤ i ≤ d − 2.

Proof. We have already shown that every f_{S}^{⋄} is in the linear span of {f_{∅}^{⋄}, f_{0}^{⋄}, f_{1}^{⋄}, …, f_{d−1}^{⋄}, f_{0,1}^{⋄}, f_{0,2}^{⋄}, …, f_{0,d−1}^{⋄}}. Now we show that every f_{0,t}^{⋄} is in the linear span of {f_{∅}^{⋄}, f_{0}^{⋄}, f_{1}^{⋄}, …, f_{d−1}^{⋄}}. Of course, Euler’s formula enables us to drop f_{d−1}^{⋄}.

The proof is by downward induction on t. We check first that it holds for t = d−1. For a multiplicial d-polytope P and any (d − 1)-face F of P, f_{0}(F) = f_{d−2}(F), since F is a multiplex. Then

f_{0,d−1}(P) = ∑_{F (d − 1)-face of P} f_{0}(F)

= ∑_{F (d − 1)-face of P} f_{d−2}(F) = f_{d−2,d−1}(P) = 2f_{d−2}(P).

Now assume for all k > t, f_{0,k}^{⋄} is in the span of {f_{∅}^{⋄}, f_{0}^{⋄}, f_{1}^{⋄}, …, f_{d−1}^{⋄}}. Since all tfaces of a multiplicial polytope are multiplexes, we get (as in the t = d−1 case) f_{0,t}^{⋄} = f_{t−1,t}^{⋄}. Now the generalized Dehn-Sommerville equations say that f_{t−1,t} − f_{t−1,t+1} + ⋯ + (−1)^{d−1−t}f_{t−1,d−1} = (1 − (−1)^{d−t})f_{t−1}. (This results from applying Euler’s formula to the quotient of the polytope P by each (t−1)-face.) By Theorem 2.1 each f_{t−1,k}^{⋄} is in the span of {f_{0}^{⋄}, f_{0,k}^{⋄}}, so by the induction hypothesis, f_{t−1,k}^{⋄} is in the span of {f_{∅}^{⋄}, f_{0}^{⋄}, f_{1}^{⋄}, …, f_{d−1}^{⋄}} for all k ≥ t + 1, so f_{t−1,t}^{⋄} = f_{0,t}^{⋄} is also in this linear span. □

Corollary 2.3. The linear span of the flag vectors of all multiplicial d-polytopes is of dimension at most d.

Computation shows that the dimension is in fact d for d ≤ 37, with the ordinary polytopes (see next section) providing a set of spanning flag vectors. Note that the induction argument in the proof of the theorem does not yield an attractive formula for the flag numbers in terms of the face numbers.

3. Flag vectors of ordinary polytopes

Of special interest among order-multiplicial polytopes are the ordinary polytopes, discovered by Bisztriczky [6]. Given an ordered set V = {x_{0}, x_{1}, …, x_{n}}, a subset Y ⊆ V is called a Gale subset if between any two elements of V \ Y there is an even number of elements of Y. A polytope P with ordered vertex set V is a Gale polytope if the set of vertices of each facet is a Gale subset.

Definition 3.1 ([6]). An ordinary polytope is a Gale polytope such that each facet is a multiplex with the induced order on the vertices.

For background on ordinary polytopes, see [2, 6, 7]. Three-dimensional ordinary polytopes are quite different from those in higher dimensions, so we will exclude them from consideration. Higher-dimensional ordinary polytopes provide a natural combinatorial generalization of cyclic polytopes, which have played such an important role in the combinatorial study of simplicial polytopes.

Theorem 3.1 ([6]). Let P be an ordinary d-polytope with ordered vertices x_{0}, x_{1}, …, x_{n}. Assume n ≥ d ≥ 4.

(1) If d is even, then P is cyclic.

(2) If d is odd, then there exists an integer k (d ≤ k ≤ n) such that the vertices sharing an edge with x_{0} are exactly x_{1}, x_{2}, …, x_{k}, and the vertices sharing an edge with x_{n} are exactly x_{n−1}, x_{n−2}, …, x_{n−k}.

From now on we will restrict our attention to ordinary polytopes of odd dimension, d = 2m+1 ≥ 5. The integer k guaranteed by this theorem is called the characteristic of the ordinary polytope. The three parameters d, k, and n completely determine the combinatorial structure of the ordinary polytope, which is denoted P^{d,k,n}. When k = d, the ordinary polytope is a multiplex. When k = n, the ordinary polytope is a cyclic polytope.

Dinh ([7]) gives an inductive geometric construction of P^{d,k,n} starting with the cyclic polytope P^{d,k,k}. He derives from this construction formulas for the face numbers f_{i} in terms of d, k, and n. We extend this method to obtain formulas for the flag numbers f_{0,t} similar to Dinh’s f-vector formulas.

Dinh successively introduces a new vertex x_{n} to produce the ordinary polytope P^{d,k,n} as conv(P^{d,k,n−1} ∪ {x_{n}}). He identifies and counts two classes of faces. A new i-face of P^{d,k,n} is an i-dimensional face of P^{d,k,n} that does not contain an i-face of P^{d,k,n−1}. An i-face of P^{d,k,n−1} destroyed by x_{n} is an i-face of P^{d,k,n−1} not contained in an i-face of P^{d,k,n}. The other faces of P^{d,k,n−1} are preserved as faces in P^{d,k,n}, either intact or with the vertex x_{n} added in the affine span.

Proposition 3.2 ([7]). The new i-faces of P^{d,k,n} are all simplices. The number of them is

α_{i}(d, k) = ∑_{j=i−m}^{⌊i/2⌋} 2N(k − 1, j, i) − N(k − 2, j, i),

where

N(s, t, u) = \binom{u − t}{t}\binom{s − u + t}{u − t} + \binom{u − 1 − t}{t}\binom{s − u + t}{u − 1 − t}.

When i ≤ m this simplifies to α_{i}(d, k) = \binom{k−1}{i} + \binom{k−2}{i−1}.

Theorem 3.3. The new i-faces of P^{d,k,n} and the destroyed i-faces of P^{d,k,n−1} are all simplices. For 0 ≤ i ≤ 2m = d − 1, the number of new i-faces minus the number of destroyed i-faces, c_{i}(d, k) = f_{i}(P^{d,k,n}) − f_{i}(P^{d,k,n−1}), is given by

c_{i}(d, k) = ∑_{j=0}^{m−1} \binom{m + 1}{i − j}\binom{k − m − 2}{j}.

When i ≤ m − 1 this simplifies to c_{i}(d, k) = \binom{k−1}{i}.

Dinh [7] first computed the quantities c_{i}(d, k), but he gave a more complicated expression. His description of the new and destroyed faces, however, lends itself to the technique used to count the faces of cyclic polytopes in [9]. After some manipulation, this yields the relatively nice form stated here. It would be good to have a bijective proof of the formula.

We also need the f-vectors of the cyclic polytopes. (See [9].)

Proposition 3.4. Let m = ⌊d/2⌋. The cyclic d-polytope with k + 1 vertices has f-vector given by

f_{i} = ϕ_{i}(d, k) = ∑_{j=0}^{m} [\binom{j}{d − 1 − i} + \binom{d − j}{d − 1 − i}] \binom{k − d + j}{j}

−χ(d even)\binom{m}{2m − 1 − i}\binom{k − m}{m}

When i ≤ m − 1 this simplifies to ϕ_{i}(d, k) = \binom{k+1}{i+1}.

Here are the f-vectors of the ordinary polytopes, as computed by Dinh.

Theorem 3.5 ([7]). Let n ≥ k ≥ d = 2m + 1 ≥ 5. The number of i-dimensional faces of the ordinary polytope P^{d,k,n} is

f_{i}(P^{d,k,n}) = ϕ_{i}(d, k) + (n − k)c_{i}(d, k),

Here are the analogous formulas for the flag numbers f_{0,i}.

Theorem 3.6. For n ≥ k ≥ d = 2m + 1 ≥ 5 and 1 ≤ i ≤ d − 1,

f_{0,i}(P^{d,k,n}) = (i + 1)ϕ_{i}(d, k)
+ (n − k)[(i + 1)c_{i}(d, k) + ϕ_{i−1}(d − 1, k − 1) − α_{i}(d, k)].

Proof. To get the number of incidences of vertices and i-faces for P^{d,k,n}, start with f_{0,i}(P^{d,k,n−1}), add the number of vertices on each new i-face, subtract the number of vertices on each destroyed i-face, and add one for each preserved i-face that now contains the new vertex x_{n}. All the new and destroyed faces are simplices, and the net gain in i-faces is c_{i}, so the contribution to the change in f_{0,i} from the new and destroyed faces is (i + 1)c_{i}. It remains to consider the preserved i-faces that now contain vertex x_{n}.

Lemma 3.7. The number of i-faces of P^{d,k,n} containing the vertex x_{n} is ϕ_{i−1}(d − 1, k − 1), the number of (i − 1)-faces of the cyclic (d − 1)-polytope with k vertices.

Proof of lemma: From the definition of ordinary polytope, it is clear that reversing the ordering of the vertices produces the same polytope. So the number of i-faces of P^{d,k,n} containing the vertex x_{n} is the same as the number of i-faces of P^{d,k,n} containing the vertex x_{0}. In Dinh’s inductive construction of P^{d,k,n} from P^{d,k,n−1}, none of the new i-faces contain x_{0}, and none of the destroyed i-faces contain x_{0}. So the number of i-faces of P^{d,k,n} containing the vertex x_{0} is the same as the number of i-faces of the cyclic polytope P^{d,k,k} containing the vertex x_{0}. The i-faces of P^{d,k,k} containing x_{0} are in one-to-one correspondence with the (i − 1)-faces of the link of vertex x_{0} in P^{d,k,k}. By Gale’s evenness condition for the facets of the cyclic polytope, the link of vertex x_{0} in the cyclic d-polytope with k + 1 vertices is the cyclic (d − 1)-polytope with k vertices. End of proof of lemma

All the new i-faces of P^{d,k,n} contain the vertex x_{n}, so the number of preserved i-faces that now contain vertex x_{n} is ϕ_{i−1}(d − 1, k − 1) − α_{i}. Since the cyclic polytope P^{d,k,k} is simplicial, f_{0,i}(P^{d,k,k}) = (i + 1)f_{i}(P^{d,k,k}) = (i + 1)ϕ_{i}(d, k). Thus

f_{0,i}(P^{d,k,n}) = f_{0,i}(P^{d,k,n−1}) + (i + 1)c_{i} + ϕ_{i−1}(d − 1, k − 1) − α_{i}
= f_{0,i}(P^{d,k,k}) + (n − k)[(i + 1)c_{i} + ϕ_{i−1}(d − 1, k − 1) − α_{i}]
= (i + 1)ϕ_{i}(d, k) + (n − k)[(i + 1)c_{i} + ϕ_{i−1}(d − 1, k − 1) − α_{i}].
□

The numbers α_{i}, c_{i} and ϕ_{i} are independent of n. So for fixed d and k, the flag vectors of the polytopes P^{d,k,n} lie on a line.

4. Toric h-vectors

We turn now to the toric h-vectors of ordinary polytopes. In the characterization of f-vectors of simplicial polytopes [4, 11], a crucial role was played by the h-vector, the image under a certain linear map of the f-vector. The h-vector can be interpreted as the sequence of homology ranks of the toric variety associated to the polytopes. In this sense (using intersection homology) the h-vector is also defined for nonsimplicial polytopes, but it depends on the flag vector, not just the f-vector. (See [3] for formulas in terms of the flag vector.) Following Stanley [12] we define the toric hvector (and g-vector) of any polytope (or Eulerian poset), first encoding the h-vector and g-vector as polynomials: h(P, t) = ∑_{i=0}^{d} h_{i}t^{d−i} and g(P, t) = ∑_{i=0}^{⌊d/2⌋} g_{i}t^{i}, with the relations g_{0} = h_{0} and g_{i} = h_{i} − h_{i−1} for 1 ≤ i ≤ d/2. Then the h-vector and g-vector are defined by the recursion

(1) g(∅, t) = h(∅, t) = 1, and

(2) h(P, t) = ∑_{{G face of P \atop G ≠ P}} g(G, t)(t − 1)^{d−1−dim G}.

The toric h-vectors of ordinary polytopes have a very simple form.

Theorem 4.1. For n ≥ k ≥ d = 2m + 1 ≥ 5 and 1 ≤ i ≤ m,

h_{i}(P^{d,k,n}) = \binom{k − d + i}{i} + (n − k)\binom{k − d + i − 1}{i − 1}.

Proof. It follows from Theorem 1.2 that the g-polynomial of the multiplex M^{d,n} is the same as the g-polynomial of the (d−2)-fold pyramid over the (n−d+3)-gon. This is the same as the g-polynomial of the (n−d+3)-gon itself, so g(M^{d,n}, t) = 1+(n−d)t. So for any multiplicial d-polytope P with n + 1 vertices,

h(P, t) = ∑_{{G face of P \atop G ≠ P}} g(G, t)(t − 1)^{d−1−dim G}

= (t − 1)^{d} + (n + 1)(t − 1)^{d−1}

+ ∑_{i=1}^{d−1} ∑_{G face of P ; dim G = i} (1 + (f_{0}(G) − 1 − i)t)(t − 1)^{d−1−i}

= (t − 1)^{d} + (n + 1)(t − 1)^{d−1} + ∑_{i=1}^{d−1} f_{i}(P)(t − 1)^{d−1−i}(1 − (i + 1)t)

+ ∑_{i=1}^{d−1} ∑_{G face of P ; dim G = i} f_{0}(G) t(t − 1)^{d−1−i}.

So for any multiplicial d-polytope P with n + 1 vertices,

h(P, t) = (t − 1)^{d} + (n + 1)(t − 1)^{d−1} + ∑_{i=1}^{d−1} f_{i}(P)(t − 1)^{d−1−i}

+ ∑_{i=1}^{d−1} (f_{0i}(P) − (i + 1)f_{i}(P)) t(t − 1)^{d−1−i}.

Now for P an ordinary polytope, substitute

n + 1 = (k + 1) + (n − k)
f_{i}(P) = ϕ_{i}(d, k) + (n − k)c_{i}(d, k)
f_{0i}(P) − (i + 1)f_{i}(P) = (n − k)[ϕ_{i−1}(d − 1, k − 1) − α_{i}(d, k)]

The result is

h(P^{d,k,n}, t) = (t − 1)^{d} + (k + 1)(t − 1)^{d−1} + ∑_{i=1}^{d−1} ϕ_{i}(d, k)(t − 1)^{d−1−i}

+ (n − k) [(t − 1)^{d−1} + ∑_{i=1}^{d−1} c_{i}(d, k)(t − 1)^{d−1−i}

+ ∑_{i=1}^{d−1}[ϕ_{i−1}(d − 1, k − 1) − α_{i}(d, k)]t(t − 1)^{d−1−i}]

= h(P^{d,k,k}) + (n − k) [∑_{i=0}^{d−1} c_{i}(d, k)(t − 1)^{d−1−i}

+ ∑_{i=1}^{d−1}[ϕ_{i−1}(d − 1, k − 1) − α_{i}(d, k)]t(t − 1)^{d−1−i}] .

The functions c_{i}(d, k), ϕ_{i−1}(d − 1, k − 1), and α_{i}(d, k) have simple expressions when i is small relative to d. This enables us to compute the high degree terms of h(P^{d,k,n}). Let A = (h(P^{d,k,n}) − h(P^{d,k,k}))/(n − k), that is,

A = ∑_{i=0}^{d−1} c_{i}(d, k)(t − 1)^{d−1−i} + ∑_{i=1}^{d−1}[ϕ_{i−1}(d − 1, k − 1) − α_{i}(d, k)]t(t − 1)^{d−1−i}.

Let A_{j} be the coefficient of t^{j} in A. To compute A_{j} for j ≥ m + 1, note that deg(t − 1)^{d−1−i} ≥ j if and only if i ≤ d − 1 − j, and deg t(t − 1)^{d−1−i} ≥ j if and only if i ≤ d − j. Thus

A_{j} = ∑_{i=0}^{d−1−j}(−1)^{d−1−i−j}\binom{d − 1 − i}{j}c_{i}(d, k)

+ ∑_{i=1}^{d−j}(−1)^{d−i−j}\binom{d − 1 − i}{j − 1}[ϕ_{i−1}(d − 1, k − 1) − α_{i}(d, k)].

For j ≥ m + 1 and i ≤ d − 1 − j, i ≤ d − m − 2 = m − 1, so we need c_{i}(d, k) only for i ≤ m − 1. For j ≥ m + 1 and i ≤ d − j, i ≤ d − m − 1 = m, so we need ϕ_{i−1}(d − 1, k − 1) − α_{i}(d, k) only for i ≤ m. For i ≤ m − 1, c_{i}(d, k) = \binom{k−1}{i}. For 1 ≤ i ≤ m, ϕ_{i−1}(d − 1, k − 1) = \binom{k}{i} and α_{i}(d, k) = \binom{k−1}{i} + \binom{k−2}{i−1}, so ϕ_{i−1}(d − 1, k − 1) − α_{i}(d, k) = \binom{k−2}{i−2}.

Thus we get the coefficient A_{j} for j ≥ m + 1,

A_{j} = (−1)^{d−1−j} ∑_{i=0}^{d−1−j}(−1)^{i} [\binom{d − 1 − i}{j}\binom{k − 1}{i} + \binom{d − 2 − i}{j − 1}\binom{k − 2}{i − 1}] .

An induction proof shows that A_{j} = \binom{k−j−1}{d−j−1} for j ≥ m + 1.

Now let i ≤ m; then d − i ≥ m + 1, so

h_{i}(P^{d,k,n}) − h_{i}(P^{d,k,k}) = h_{d−i}(P^{d,k,n}) − h_{d−i}(P^{d,k,k})
= (n − k)\binom{k − d + i − 1}{i − 1}.

Since h_{i}(P^{d,k,k}) = \binom{k−d+i}{i} for i ≤ m,

h_{i}(P^{d,k,n}) = \binom{k − d + i}{i} + (n − k)\binom{k − d + i − 1}{i − 1}. □

Among all d-polytopes with n+1 vertices, the minimum h-vector has h_{i} = n−d+1 for all i, 1 ≤ i ≤ d − 1; this is the h-vector of the multiplex. The maximum hvector (for d odd) has h_{i} = \binom{n−d+i}{i} for 1 ≤ i ≤ (d − 1)/2; this is the h-vector of the cyclic polytope. The ordinary polytopes provide a nice distribution of hvectors between these two extremes. Note that the g-vector satisfies the relation g_{i}(P^{d,k,n}) = h_{i}(P^{d,k−1,n−1}).

5. Multiplicial Polytopes with a Large Facet

The facets of ordinary d-polytopes are “small”: each has at most 2d − 2 vertices. Bisztriczky raised the question of whether there exist order-multiplicial polytopes with a large proportion of the vertices on a single facet. The corresponding question for weakly multiplicial polytopes is trivial, since the pyramid over a multiplex is a weakly multiplicial polytope (but is not generally an order-multiplicial polytope). We give here a construction of order-multiplicial 4-polytopes having two-thirds of their vertices on one facet.

Theorem 5.1. For every integer q ≥ 5, there is an order-multiplicial 4-polytope with q vertices having a facet containing ⌈(2q + 2)/3⌉ vertices.

Proof. First note that the result is obtained for q = 5 and q = 6 by multiplexes (the simplex, and the double pyramid over a square, respectively). So assume q ≥ 7. We show in detail the construction for q ≡ 1 (mod 3), and then give the modifications for the other congruence classes. So let q ≡ 1 (mod 3), q ≥ 7. Let n = (2q + 1)/3. Let M^{3,n} be a 3-multiplex with vertices labeled by the integers {0, 1, 2, …, q − 1} \ {3j : 1 ≤ j ≤ (q − 2)/3}, with the standard (<) order. Let Q_{0} be a pyramid over the 3-multiplex with apex labeled 3, Q_{0} = P (M^{3,n}). Now Q_{0} is (weakly) multiplicial, but not order-multiplicial. We perform some subdivisions on Q_{0} to achieve order-multipliciality. The polytope Q_{0} has three kinds of facets: the multiplex M^{3,n} itself, simplices, and pyramids over quadrilateral faces of M^{3,n}. The multiplex and the simplices are multiplexes in the induced order; the pyramids in general are not. Note that the “first” two pyramidal facets are multiplexes in the induced order; their vertex sets are {0, 1, 3, 4, 5} and {1, 2, 3, 5, 7} (or, rather, {1, 2, 3, 5, 6}, if q = 7).

We pair up the remaining pyramidal facets and add a new vertex beyond each pair. For each i, 0 ≤ i ≤ (q−10)/3, let F_{i} be the convex hull of {2+3i, 4+3i, 7+3i, 8+3i, 3}, and let G_{i} be the convex hull of {4 + 3i, 5 + 3i, 8 + 3i, 10 + 3i, 3} (or, rather, G_{i} = {4 + 3i, 5 + 3i, 8 + 3i, 9 + 3i, 3}, if i = (q − 10)/3). Note that these two facets share the 2-face with vertex set {4 + 3i, 8 + 3i, 3}. Choose a point beyond F_{i} and G_{i} and beneath all other facets of Q_{0}, and label it 6 + 3i. Let Q_{i+1} be the convex hull of Q_{i} with the new vertex 6 + 3i. By [1], the facets of Q_{i+1} consist of the facets of Q_{i}, except F_{i} and G_{i}, and eight additional facets, with vertex sets {2+3i, 4+3i, 6+3i, 3}, {2 + 3i, 6 + 3i, 7 + 3i, 3}, {6 + 3i, 7 + 3i, 8 + 3i, 3}, {2 + 3i, 4 + 3i, 6 + 3i, 7 + 3i, 8 + 3i}, {4 + 3i, 5 + 3i, 6 + 3i, 3}, {5 + 3i, 6 + 3i, 10 + 3i, 3}, {6 + 3i, 8 + 3i, 10 + 3i, 3}, and {4+3i, 5+3i, 6+3i, 8+3i, 10+3i}. (Here, 10+3i should be replaced by 9+3i in each set, if i = (q − 10)/3.) After performing this operation for all i, 0 ≤ i ≤ (q − 10)/3, all the pyramidal facets of Q_{0} are replaced by collections of simplices (necessarily multiplexes), and by pyramidal facets that are now multiplexes with the induced order. Thus the resulting polytope, P = Q_{(q−10)/3+1} is an order-multiplicial polytope. The polytope Q_{0} has n+2 vertices, and (q −10)/3+1 vertices have been added. The polytope P has exactly q vertices. Of those q vertices, n+1 = (2q+4)/3 = ⌈(2q+2)/3⌉ are vertices of the original base facet M^{3,n}.

For q ≡ 2 (mod 3) (q ≥ 8), let n = (2q − 1)/3. We proceed as before with Q_{0} = P (M^{3,n}), adding vertices labeled 6 + 3i for 0 ≤ i ≤ (q − 11)/3 for each facet pair F_{i}, G_{i}. Finally we choose a point beyond the “last” facet F, which is a simplex with vertex set {q − 4, q − 3, q − 1, 3}, and beneath all other facets, and label it q − 2. Let P be the convex hull of Q_{(q−11)/3+1} with the new vertex q − 2. The facets of P consist of the facets of Q_{(q−11)/3+1}, except F, and four additional facets, all of which are simplices. The resulting polytope P is an order-multiplicial polytope with exactly q vertices. Of those q vertices, n + 1 = (2q + 2)/3 = ⌈(2q + 2)/3⌉ are vertices of the original base facet M^{3,n}.

If q ≡ 0 (mod 3) (q ≥ 9), let n = 2q/3. The polytope Q_{0} = P (M^{3,n}) has an odd number of pyramidal facets. We proceed as before, adding vertices labeled 6 + 3i for 0 ≤ i ≤ (q − 12)/3 for each facet pair F_{i}, G_{i}. The last pyramidal facet F has vertex set {q −7, q −5, q −2, q −1, 3}. Choose a point beyond F and beneath all other facets of Q_{(q−12)/3+1}, and label it q − 3. Let P be the convex hull of Q_{(q−12)/3+1} with the new vertex q − 3. The facets of P consist of the facets of Q_{(q−12)/3+1}, except F, and five additional facets, with vertex sets {q − 7, q − 5, q − 3, 3}, {q − 7, q − 3, q − 2, 3}, {q − 5, q − 3, q − 1, 3}, {q − 3, q − 2, q − 1, 3}, and {q − 7, q − 5, q − 3, q − 2, q − 1}. The resulting polytope P is an order-multiplicial polytope with exactly q vertices. Of those q vertices, n + 1 = (2q + 3)/3 = ⌈(2q + 2)/3⌉ are vertices of the original base facet M^{3,n}.

□

For q ≥ 7, q ≢ 0 (mod 3), the f-vector of this multiplicial 4-polytope is

f(P) = (q, ⌊\frac{13q − 43}{3}⌋ , 6q − 26, ⌊\frac{8q − 34}{3}⌋)

and f_{02} = ⌊(56q − 242)/3⌋. For q ≥ 9, q ≡ 0 (mod 3), the f-vector is

f(P) = (q, \frac{13q − 45}{3}, 6q − 27, \frac{8q − 36}{3})

and f_{02} = (56q − 252)/3. The h-vector is h = (1, q − 4, 2q − 12, q − 4, 1), unless q ≡ 1 (mod 3), in which case it is h = (1, q − 4, 2q − 11, q − 4, 1).

6. Conclusion

We hope that multiplicial polytopes can be used to further our understanding of the set of all flag vectors of polytopes. Ordinary polytopes seem particularly important because they generalize cyclic polytopes, which have played a major role in the study of simplicial polytopes (see [4, 8, 9, 10]). From the viewpoint of flag vectors, the restriction to odd dimensions is unfortunate. However, even-dimensional polytopes can be generated by taking vertex figures of the odd-dimensional ordinary polytopes. The resulting polytopes are multiplicial.

References

[1] Amos Altshuler and Ido Shemer. Construction theorems for polytopes. Israel J. Math., 47 (1984), 99–110.

[2] Margaret M. Bayer, Aaron M. Bruening, and Joshua D. Stewart, A combinatorial study of multiplexes and ordinary polytopes, Discrete Comput. Geom., 27 (2002), no. 1, 49–63.

[3] Margaret M. Bayer and Richard Ehrenborg, The toric h-vectors of partially ordered sets, Trans. Amer. Math. Soc. 352 (2000), 4515–4531.

[4] Louis J. Billera and Carl W. Lee, A proof of the sufficiency of McMullen’s conditions for f-vectors of simplicial polytopes, J. Combin. Theory Ser. A 31 (1981), 237–255.

[5] T. Bisztriczky. On a class of generalized simplices. Mathematika, 43 (1996), 274–285.

[6] T. Bisztriczky. Ordinary (2m + 1)-polytopes. Israel J. Math., 102 (1997), 101–123.

[7] Thi Ngoc Dinh. Ordinary Polytopes. PhD thesis, The University of Calgary, 1999.

[8] Branko Grünbaum. Convex Polytopes, Second Edition, Springer-Verlag, New York, 2003.

[9] P. McMullen and G. C. Shephard, Convex polytopes and the upper bound conjecture, Cambridge Univ. Press, London, 1971.

[10] Jörg Rambau and Francisco Santos. The generalized Baues problem for cyclic polytopes. I. European J. Combin., 21 (2000), 65–83.

[11] Richard P. Stanley, The number of faces of simplicial convex polytopes, Adv. Math. 35 (1980), 236–238.

[12] Richard P. Stanley. Generalized H-vectors, intersection cohomology of toric varieties, and related results. In Commutative algebra and combinatorics (Kyoto, 1985), volume 11 of Adv. Stud. Pure Math., pages 187–213, Amsterdam-New York, 1987. North-Holland.

Department of Mathematics, University of Kansas, Lawrence, KS 66045-7523

 E-mail address: bayer@math.ukans.edu