Polyhedral Subdivisions and Projections of Polytopes Jörg Rambau Dissertation (Advisor: Günter M. Ziegler, TU Berlin)

     
Cyclic Polytopes

In this section we recall the basic definitions and theorems related to cyclic polytopes in a combinatorial language.

Definition 3.3.1   Let $\mathcal{L}$ be a linearly ordered set, and let $t: \mathcal{L} \to \mathbb{R}$, $i \mapsto t_i$ be a strictly monotone function.

The $d$-dimensional   cyclic polytope $C(\mathcal{L},d,t)$, labelled by  $\mathcal{L}$, parametrized by $t$ is the convex hull of the points $\nu _d (t_1), \dots , \nu _d (t_n)$ with

$$\nu _d (x) := (x, x^2, \dots , x^d) \in \mathbb{R} ^d.$$

For simplicity, we set $C(n,d,t) := C([n],d,t)$.

The main reason for the fact that triangulations of cyclic polytopes can be treated effectively in a purely combinatorial way are the following well-known properties that follow from the special structure of Vandermonde-determinants.

The first one -- Gale's famous Evenness Criterion -- characterizes the set $\mathcal{F}_{\nu _d \circ t}$of all combinatorial facets of $C(\mathcal{L},d,t)$. The following notion allows us to state that criterion in a compact way.

Definition 3.3.2   Let $L$ be a linearly ordered set and $S$ a subset of $L$. An element $s_0 \in \complement S$ is an   even gap in $S$ if $\char93 \setof{s \in S}{s > s_0}$ is even, otherwise it is an   odd gap.

 

Theorem 3.3.3 (Gale's Evenness Criterion)   [32] An ordered subset $F$ of the vertex set of the cyclic polytope $C(\mathcal{L},d,t)$ is a facet if and only if between any two vertices not in $F$ there is an even number of vertices in $F$. Equivalently, $F$ is a facet of $C(\mathcal{L},d,t)$ if and only if either all gaps in $F$ are even or all gaps in $F$ are odd.

The second one describes the form of those sets of vertices of $C(\mathcal{L},d,t)$ whose convex hulls intersect in the relative interior of both. Hence, this determines $\mathcal{C}_{\nu _d \circ t}$.

Theorem 3.3.4   [15] The circuits of $C(\mathcal{L},d,t)$ are the alternating $(d+2)$-subsets of $\mathcal{L}$, i. e., the pairs $(Z^o,Z^e)$ and $(Z^e,Z^o)$, where $Z^o$ is the set of odd elements $(z_1, z_3, z_5, \dotsc )$, and $Z^e$ is the set of even elements $(z_2, z_4, z_6, \dotsc )$ of $Z = (z_1, \dots , z_{d+2})$.

The combinatorial polytopes $\mathcal{P}(\nu _d \circ t)$ are identical for all $t$ because the strictly monotone function $t$ does not affect the assertions of these criteria. This means that the combinatorial study of triangulations of cyclic polytopes with any parametrization is equivalent to the investigation of combinatorial triangulations of the combinatorial polytopes $\mathcal{P}(\nu _d \circ t)$.

Definition 3.3.5   The combinatorial polytope $C(\mathcal{L},d) := \mathcal{P}(\nu _d \circ t)$ of $\nu _d \circ t: \mathcal{L} \to \mathbb{R} ^d$ is called the   cyclic $d$-polytope with vertices labelled by  $\mathcal{L}$. The set of its combinatorial facets is denoted by $\mathcal{F}(\mathcal{L},d)$, the set of its circuits is written as $\mathcal{Z}(\mathcal{L},d)$. Those combinatorial facets with only odd gaps are the   upper facets, the set of which is denoted by $\mathcal{F}^u(\mathcal{L},d)$; those with only even gaps are the   lower facets of $C(\mathcal{L},d)$, denoted by $\mathcal{F}^l(\mathcal{L},d)$.

The set of circuits $Z$ with maximal element $z_{d+2}$ in $Z^+$ is denoted by $\mathcal{Z}^+(n,d)$, the set of circuits having their maximal element in $Z^-$ is written as $\mathcal{Z}^-(n,d)$. The cyclic polytope labelled by $[n]$ is denoted by $C(n,d)$.

Note that in odd dimensions there are polytopes that have the same face lattice as $C(n,d,t)$ but a different circuit structure (see [15]); this leads to completely different triangulations.

Remark 3.3.6   Geometric Meaning (see Figure 3.1): Consider for some strictly monotone $t: [n] \to \mathbb{R}$ the   projection

$$p = p(n,d): \left\{ \begin{array}{rcl} C(n,d+1,t) & \to & ... ...x_{d+1}) & \mapsto & (x_1, \dots , x_d). \end{array} \right.$$

Moreover, consider for some geometric triangulation $\Delta$ of $C(n,d,t)$ the unique piecewise linear section (linear on each simplex $\sigma \in \Delta$)

$$s_{\Delta}: \left\{ \begin{array}{rcl} C(n,d,t) & \to & C(... ...igr), \quad \forall \sigma \in \Delta . \end{array} \right.$$

Then any triangulation $\Delta$ of $C(n,d,t)$ can be recovered from its   characteristic section  $s_{\Delta}$.

The upper facets $\mathcal{F}^u(n,d+1)$ of $C(n,d+1)$ are the sets of those facets of $C(n,d+1,t)$ that can be seen from a point in $\mathbb{R} ^{d+1}$ with large positive $(d+1)$-th coordinate (geometric upper facets of $C(n,d+1,t)$), the lower facets $\mathcal{F}^u(n,d+1)$ label the sets of those facets of $C(n,d+1,t)$ that can be seen from a point in $\mathbb{R} ^{d+1}$ with large negative $(d+1)$-th coordinate (geometric lower facets of $C(n,d+1,t)$). The geometric upper (respectively lower) facets project down to $C(n,d,t)$ without overlapping. Therefore, their projections define geometric triangulations of $C(n,d,t)$.

  

Figure 3.1: The canonical projection $p: C(5,3) \to C(5,2)$ and characteristic sections corresponding to triangulations of $C(5,2)$.

The support $\supp(Z)$ of any circuit  $Z = (Z^+, Z^-)$ in $C(n,d)$ corresponds to the label set of a unique $(d+1)$-simplex in $C(n,d+1,t)$ where its set of geometric upper facets belongs to the elements of the star of the positive part $Z^+$ in $\supp(Z)$, and its set of geometric lower facets corresponds to the elements of the star of the negative part $Z^-$ in $\supp(Z)$.

Lemma 3.3.7   (Elementary Facts)

(i)

  $\mathcal{F}^l(n,d+1)$ and $\mathcal{F}^u(n,d+1)$ are combinatorial triangulations of the cyclic polytope $C(n,d)$.

(ii)

  Every facet in $\mathcal{F}^u(n,d)$ contains $n$.

(iii)

  If a pair of simplices $S_1$ and $S_2$ is not admissible then there exists a circuit in $\mathcal{Z}(n,d)$ with maximal element $z_{d+2} = \max (S_1 \cup S_2)$.

(iv)

  If a $(d-1)$-simplex $F$ is the common facet of the admissible pair $(S_1,S_2)$ then $S_1 \sm F$ lies in an odd gap of $F$ and $S_2 \sm F$ lies in an even gap of $F$, or vice versa.

Remark 3.3.8   The circuits of $C(n,d)$ can be visualized in a table that consists of columns numbered from $1$ to $n$ and rows corresponding to $Z^+$ and $Z^-$, where a star ``$*$'' in column $i$ and row $Z^{\epsilon}$ means that $i \in Z^{\epsilon}$, $\epsilon \in \{+,-\}$. The stars can then be connected by a zig-zag-path with $(d+2)$ nodes. For example, if $n = 6$, $d = 3$, and $Z = ((1,3,5), (2,4))$ we get the following table:

$$\begin{array}[b]{\vert c\vert\vert*{6}{c\vert}} \hline & 1 ... ... & & * & \\ \hline Z^- & & * & & * & & \\ \hline \end{array}$$

If the rows are filled with stars corresponding to two simplices then these two simplices are admissible if and only if each zig-zag-path connects at most $(d+1)$ stars. For instance, if $n = 6$, $d = 3$, $S = (1,3,4,5)$, and $S' = (2,3,4,6)$ the table looks as follows:

$$\begin{array}[b]{\vert c\vert\vert*{6}{c\vert}} \hline & 1 ... ... & * & \\ \hline S' & & * & * & * & & *\\ \hline \end{array}$$

The reader will easily find a zig-zag-path connecting even $6 > d+2$ stars, showing that $S,S'$ is not an admissible pair.

Obviously all $C(\mathcal{L},d)$ with $\char93 \mathcal{L} = n$are isomorphic to $C(n,d)$. From now on we are exclusively dealing with combinatorial triangulations of $C(n,d)$, and we will leave out the ``combinatorial'' attribute whenever this is not confusing.

The following Propositions -- consequences of Theorems 3.3.3 and 3.3.4 -- relate cyclic polytopes with different parameters. We use the notation $F = (f_1, \dots , f_d)$ for $F \in \mathcal{F}(n,d)$ and $Z = (z_1, \dots , z_{d+2})$ for $Z \in \mathcal{Z}(n,d)$.

 

Proposition 3.3.9   (Functorial Facet Properties) $$\begin{align*}\mathcal{F}^u(n+1,d+1) &= \mathcal{F}^l(n,d) * \{ n+1 \},\\ \mat... ... \mathcal{F}^l(n-1,d) &= \as_{\mathcal{F}^l(n,d)}(n). \tag*{\qed} \end{align*}$$

 

Proposition 3.3.10   (Functorial Circuit Properties) $$\begin{align*}\mathcal{Z}^+(n+1,d+1) &= \setof{ (Z^+ \cup \{j\},Z^-)}{(Z^+,Z^-... ...(Z^+,Z^-) \in \mathcal{Z}^-(n,d)}{n \notin \supp(Z)}. \tag*{\qed} \end{align*}$$

The following proposition is the combinatorial description for the geometric connection provided by the projection $p(n,d)$between $(d+1)$-simplices in $C(n,d,t)$ and the minimal affine dependencies in $C(n,d,t)$.

 

Proposition 3.3.11   (Functorial Circuit-Facet Relations) For $Z \in \mathcal{Z}^+(n,d)$ and $\supp(Z)$ considered as a simplicial complex, we have $$\begin{align*}\st_{\supp(Z)}(Z^+) &= \mathcal{F}^u(\supp(Z),d+1),\\ \st_{\supp(Z)}(Z^-) &= \mathcal{F}^l(\supp(Z),d+1). \tag*{\qed} \end{align*}$$