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 be a linearly ordered set, and let , be a strictly monotone function.

The -dimensional   cyclic polytope , labelled by  , parametrized by is the convex hull of the points with

For simplicity, we set .

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 of all combinatorial facets of . The following notion allows us to state that criterion in a compact way.

Definition 3.3.2   Let be a linearly ordered set and a subset of . An element is an   even gap in if is even, otherwise it is an   odd gap.

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

The second one describes the form of those sets of vertices of whose convex hulls intersect in the relative interior of both. Hence, this determines .

Theorem 3.3.4   [15] The circuits of are the alternating -subsets of , i. e., the pairs and , where is the set of odd elements , and is the set of even elements of .

The combinatorial polytopes are identical for all  because the strictly monotone function 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 .

Definition 3.3.5   The combinatorial polytope of is called the   cyclic -polytope with vertices labelled by  . The set of its combinatorial facets is denoted by , the set of its circuits is written as . Those combinatorial facets with only odd gaps are the   upper facets, the set of which is denoted by ; those with only even gaps are the   lower facets of , denoted by .

The set of circuits with maximal element in is denoted by , the set of circuits having their maximal element in is written as . The cyclic polytope labelled by  is denoted by .

Note that in odd dimensions there are polytopes that have the same face lattice as 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 the   projection

Moreover, consider for some geometric triangulation of the unique piecewise linear section (linear on each simplex )

Then any triangulation of can be recovered from its   characteristic section  .

The upper facets of are the sets of those facets of that can be seen from a point in with large positive -th coordinate (geometric upper facets of ), the lower facets label the sets of those facets of that can be seen from a point in with large negative -th coordinate (geometric lower facets of ). The geometric upper (respectively lower) facets project down to without overlapping. Therefore, their projections define geometric triangulations of .

The support of any circuit  in corresponds to the label set of a unique -simplex in where its set of geometric upper facets belongs to the elements of the star of the positive part  in , and its set of geometric lower facets corresponds to the elements of the star of the negative part  in .

Lemma 3.3.7   (Elementary Facts)
(i)
and are combinatorial triangulations of the cyclic polytope .
(ii)
Every facet in contains .
(iii)
If a pair of simplices and is not admissible then there exists a circuit in with maximal element .
(iv)
If a -simplex  is the common facet of the admissible pair then lies in an odd gap of  and lies in an even gap of , or vice versa.

Remark 3.3.8   The circuits of can be visualized in a table that consists of columns numbered from to  and rows corresponding to and , where a star '' in column  and row means that , . The stars can then be connected by a zig-zag-path with nodes. For example, if , , and we get the following table:

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 stars. For instance, if , , , and the table looks as follows:

The reader will easily find a zig-zag-path connecting even stars, showing that is not an admissible pair.

Obviously all with are isomorphic to . From now on we are exclusively dealing with combinatorial triangulations of , 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 for and for .

Proposition 3.3.9   (Functorial Facet Properties)

Proposition 3.3.10   (Functorial Circuit Properties)

The following proposition is the combinatorial description for the geometric connection provided by the projection between -simplices in and the minimal affine dependencies in .

Proposition 3.3.11   (Functorial Circuit-Facet Relations) For and considered as a simplicial complex, we have

Last Update: March 20, 1998 by Jörg Rambau