ON SUBDIVISION POSETS OF CYCLIC POLYTOPES

PAUL H. EDELMAN, JÖRG RAMBAU, AND VICTOR REINER

Abstract. There are two related poset structures, the higher Stasheff-Tamari orders, on the set of all triangulations of the cyclic d polytope with n vertices. In this paper it is shown that both of them have the homotopy type of a sphere of dimension n − d − 3.

Moreover, we resolve positively a new special case of the Generalized Baues Problem: The Baues poset of all polytopal decompositions of a cyclic polytope of dimension d ≤ 3 has the homotopy type of a sphere of dimension n − d − 2.

1. Introduction

This paper continues the investigation of certain posets of triangulations of cyclic polytopes, the higher Stasheff Tamari posets, initiated in [4] and continued in [5].

The first higher Stasheff Tamari poset is the poset S_{1}(n,d) of all triangulations of the cyclic d-polytope with n vertices C(n,d), partially ordered by increasing bistellar operations; the second higher Stasheff Tamari poset is the poset S_{2}(n,d) of all triangulations of C(n,d), partially ordered by the height of their characteristic sections in C(n,d + 1) (see [4], [5]).

Our first main result is the following.

Theorem 1.1. (i) For all n > d + 1 the proper part \overline{S_{1}(n,d)} of S_{1}(n,d) is homotopy

equivalent to a sphere of dimension n − d − 3. (ii) For all n > d + 1 the proper part \overline{S_{2}(n,d)} of S_{2}(n,d) is homotopy equivalent to a

sphere of dimension n − d − 3.

In [4], it was proved for d ≤ 3 that the poset structures S_{1}(n,d) and S_{2}(n,d) coincide. It was also shown that the poset S_{2}(n,d) is a lattice for d ≤ 3. If d = 2 this is the wellknown Tamari lattice on triangulations of a convex n-gon. We will use this lattice structure to resolve in the affirmative a special case of the Generalized Baues Problem of Billera, Kapranov, and Sturmfels (see [1], [6], [8]).

Theorem 1.2. For cyclic polytopes C(n,d) of dimension d ≤ 3, the refinement ordering on the set of polytopal subdivisions gives a poset which is homotopy equivalent to a (n − d − 2)-sphere.

The second author was supported at MSRI in part by NSF grant #DMS 9022140.

The third author was supported by a Univ. of Minnesota McKnight-Land Grant Fellowship.

We will prove Theorem 1.1 by induction on n−d, showing that the poset \overline{S_{1}(n,d)}(resp. \overline{S_{2}(n,d)}) is homotopy equivalent to the suspension of \overline{S_{1}(n − 1,d)} (resp. \overline{S_{2}(n − 1,d)}).

The proof of Theorem 1.2 is via a reduction to the poset \overline{S_{2}(n,d)}, by showing that the poset of polytopal subdivisions of C(n,d) is homotopy equivalent to the suspension of \overline{S_{2}(n,d)}. We will make use of a lemma (Lemma 6.5) about the homotopy type of noncontractible intervals in a poset which we think is of interest in its own right.

This paper is structured as follows: in Section 2 we recall some notation and basic facts about simplicial complexes, posets, and cyclic polytopes. In Section 3 we prove Theorem 1.1. Sections 4 and 5 provide the necessary details. In Section 6 we prove Theorem 1.2, the special case of the Generalized Baues Problem. Section 7 discusses some of the remaining open problems in the area of triangulations of cyclic polytopes.

2. Notation and Basic Facts

In this section we will introduce our notation and discuss some basic facts that have appeared previously.

Let [n] := {1,2,... ,n}. We regard the cyclic d-polytope with n vertices as the convex hull of points on the moment curve

C(n,d) = conv{(i,i^{2},...,i^{d}) ∈ ℝ^{d} : i ∈ [n]}

Since we are dealing with the combinatorial structure of all triangulations of cyclic polytopes we may choose these special coordinates without any loss of generality. We will often refer to the i^{th} vertex (i,i^{2},... ,i^{d}) of C(n,d) as simply i.

The canonical projection p = p_{n,d} from C(n,d + 1) onto C(n,d) is given by deletion of the x_{d+1} -coordinate. Facets of C(n,d) that can be seen from a point in ℝ^{d+1} with a very large (negative) x_{d+1} -coordinate are called upper (lower) facets.

Two simplices are said to be admissible if they intersect in a common (possibly empty) face of each. A triangulation of a polytope P is a set of simplices with vertices in the vertex set of P such that

• the union of the simplices equals P,

• every face of a simplex in the triangulation is itself in the triangulation, and

• any two simplices are admissible.

Triangulations are often identified with their sets of inclusion-maximal faces. Simplices are usually identified with their vertex sets.

To test intersections of simplices S_{1} and S_{2} we will use the concept of zig-zag-paths based on the alternating oriented matroid property of cyclic polytopes (see [5]). We construct a table with n columns, corresponding to the labels 1,...,n, and two rows, corresponding to the simplices S_{1} and S_{2}. In row i, column j, there is a star ∗ if and only if j ∈ S_{i}. An (S_{1},S_{2})-zig-zag-path of length k is a set of k stars in the columns s_{1} < ···< s_{k} such that s_{1},s_{3},s_{5},... are in S_{1} and s_{2},s_{4},s_{6},... are in S_{2}, or vice versa. The simplices

(b) (a) S_{1} S_{2} 1 2 3 4 5 6 7 8 9  1 2 3 4 5 6 7 8 9 S_{2} S_{1} ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗  ∗ ∗  ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗

Figure 1. Zig-zag-paths: (a) S_{1} and S_{2} are non-admissible in dimensions 5 or less, hence S_{1} and S_{2} cannot be in a triangulation of, e. g., C(9,4) at the same time; (b) S_{1} and S_{2} are admissible in dimensions 3 or greater, therefore S_{1} and S_{2} may be in a triangulation of C(9,4).

(b) (a) 1 2 3 4 5 6 7 8 9  1 2 3 4 5 6 7 8 9 o eo e e o o e  e  eo o ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗  ∗ ∗ ∗  ∗ ∗ ∗ ∗ ∗ ∗ S_{1} S_{2}  S_{1} S_{2}

Figure 2. Gaps: (a) S_{1} is a lower facet of C(9,4), S_{2} is an upper facet of C(9,4); (b) neither S_{1} nor S_{2} are facets of C(9,4), but S_{1} is a lower facet and S_{2} an upper facet of the cyclic subpolytope C({2,3,6,7,8,9},4). Therefore, S_{1} is lower than S_{2} in C(9,5).

S_{1} and S_{2} are admissible in dimension d if and only if there is no (S_{1},S_{2})-zig-zag-path of length d + 2 (see Figure 1).

Any subset V ⊆ [n] gives rise to a cyclic subpolytope C(V,d), namely the convex hull of the subset V. For a cyclic subpolytope C(V,d) and a d-subset F of V we call a label i ∈ V \F an even (odd) gap of F (in V) if the number of labels j ∈ V with j > i is even (odd). Then we know that the set of lower (upper) facets of C(V,d) is the set of all F ∈ \binom{V}{d} containing only even (odd) gaps [5]. This applies, in particular, to simplices so that we can talk about the upper and lower facets of a d-simplex in C(n,d). For a visualization, we use the same table as for the zig-zag-paths and fill an e (resp. o) for an even (resp. odd) gap into the corresponding field (see Figure 2).

Let T be a triangulation of C(n,d) and S̃be a (d +1)-simplex in C(n,d +1) all of whose lower facets lie in T. An increasing bistellar operation or increasing flip in T at S̃is an operation that replaces in T the lower facets of S̃by the upper facets of S̃. The result, it is clear, is a new triangulation of C(n,d). The transitive closure of this operation defines the first higher Stasheff-Tamari poset S_{1}(n,d). We write T <_{1} T′to indicate that T is less than T′in S_{1}(n,d).

The characteristic section of a triangulation T of C(n,d) is the unique piecewise linear map (with respect to the simplicial complex T) from C(n,d) to C(n,d + 1) that is inverted by the canonical projection p and has the property that it sends the i^{th} vertex of C(n,d) to the i^{th} vertex of C(n,d + 1). We identify a triangulation T with its characteristic section T : C(n,d) → C(n,d + 1) and with its image T (C(n,d)) in C(n,d + 1). The second higher Stasheff-Tamari poset S_{2}(n,d) is the set of all triangulations of C(n,d) partially ordered by the height of characteristic sections. That is, T ≤_{2} T′if and only if T (x)_{d+1} ≤ T′(x)_{d+1} for all x ∈ C(n,d), where here v_{d+1} denotes the (d + 1)^{st} coordinate of the vector v in ℝ^{d+1} . We then say that T is weakly lower than T′. If T (x)_{d+1} ≤ T′(x)_{d+1} holds for all x in the (geometric) intersection of a simplex S ∈ T and a simplex S′∈ T′we say that S is weakly lower than S′. We write T <_{2} T′to denote that T is less than T′in S_{2}(n,d).

The unique minimal element in S_{1}(n,d) respectively S_{2}(n,d) (which is the set of lower facets of C(n,d + 1)) is denoted by ˆ0_{n,d}. Similarly, the unique maximal element (which is the set of upper facets of C(n,d + 1)) is denoted by ˆ1_{n,d}. The d-simplices in C(n,d) are partially ordered by the following relation: S ≺ S′if and only if S ∩ S′is a lower facet of S′ and an upper facet of S (see [5]).

We will make use of some standard constructions on simplicial complexes. Let Δ be a simplicial complex on the ground set X. That is, Δ is a collection of subsets of X that is closed under containment. If S ⊆ X define the link of S in Δ to be the complex

lk_{Δ}(S) := {R\S: R ∈ Δ,S ⊆ R };

the star of S in Δ is the complex

st_{Δ}(S) := {R ∈ Δ : S ⊆ R };

and the deletion of S in Δ is the complex

del_{Δ}(S) := {R ∈ Δ : S ⊈ R }.

If there is another complex Δ′on a ground set Y disjoint from X we will define the combinatorial join of Δ and Δ′to be the complex on the ground set X ∪ Y

Δ ∗ Δ′:= {S ∪ S′ : S ∈ Δ,S′∈ Δ′ }.

If T,T′are the sets of inclusion maximal faces of Δ,Δ′then the above formulas yield the sets of inclusion maximal faces of the link, the star, the deletion, and the join, respectively.

Given an i-simplex σ spanned by some (i + 1)-subset (also denoted σ) of vertices of C(n,d), there is also a unique linear section σ: σ → C(n,d + 1) of p having the property that it sends each vertex i of σ to the vertex labelled i of C(n,d +1). Say that σ submerged by the triangulation T of C(n,d) if

σ(x)_{d+1} ≤ T (x)_{d+1}

for every point x in σ. For a triangulation T of C(n,d) let its i^{th}submersion set sub_{i}(T) be the set of i-simplices submerged by T.

When we refer to the topology or homotopy type of a poset P, we will always mean the topology of the geometric realization of its order complex, i. e., |Δ(P)| [3, §9]. If P is a poset with bottom and top elements ˆ0, ˆ1, then its proper part \overline{P} is simply the subposet P\{ˆ0, ˆ1}.

We recall the following facts from [4] and [5] which will be crucial for our main results:

Theorem 2.1. [5, Theorem 1.1] The first higher Stasheff Tamari poset S_{1}(n,d) is bounded.

Theorem 2.2. [5, Theorem 4.2(iii), Proposition 5.14(iii)] The following map is well-defined and order-preserving:

f : \{ \begin{matrix}S_{1}(n,d) & → & S_{1}(n − 1,d), \\ T & ↦ & del_{T}(n) ∪ (del_{lk_{T}(n)}(n − 1) ∗ \{n − 1\}) . \end{matrix}

Proposition 2.3. [4, Proposition 2.15 ] For any two triangulations T_{1},T_{2} of C(n,d), we have T_{1} ≤ T_{2} in S_{2}(n,d) if and only if

sub_{⌈ \frac{d}{2}⌉}(T_{1}) ⊆ sub_{⌈ \frac{d}{2}⌉}(T_{2}).

Proposition 2.4. [4, Propositions 3.2, 4.1 ] Membership in ⌈\frac{d}{2}⌉- submersion sets for d = 2,3 has the following characterization.

For T a triangulation of C(n,2) and e = {i,j} an edge inside C(n,2), we have that e ∈ sub_{1}(T) if and only if there does not exist an edge e′= {k,l} of T with k < i < l < j.

For T a triangulation of C(n,3) and t = {i,j,k} a triangle inside C(n,3), we have that t ∈ sub_{2}(T) if and only if there does not exist an edge {x,y} of T with i < x < j < y < z.

Theorem 2.5. [4, Theorems 3.6, 4.9] For d ≤ 3, the higher Stasheff-Tamari poset S_{2}(n,d) is a lattice, i. e., any subset of its elements has a meet (greatest lower bound) and a join (least upper bound).

Theorem 2.6. [4, Theorems 3.9, 4.11] For d ≤ 3, the proper part \overline{S_{2}(n,d)}of the higher Stasheff-Tamari poset has the homotopy type of an (n − d − 3)-sphere.

3. The Homotopy Types of S_{1}(n,d) and S_{2}(n,d)

In this section, Theorem 1.1 will be proven by induction on n − d, using the Suspension Lemma 3.1 below to show that the proper part of S(n,d) is homotopy equivalent to the suspension of the proper part of S(n−1,d), where S(n,d) can be either S_{1}(n,d) or S_{2}(n,d). (A more detailed proof of the Suspension Lemma can be found in [7].)

Lemma 3.1 (Suspension Lemma). Let P,Q be bounded posets with ˆ0_{Q} ≠ ˆ1_{Q}. Assume there exist a dissection of P into green elements green(P) and red elements red(P), as well as order-preserving maps

f : P → Q and i,j: Q → P

with the following properties:

(i) The green elements form an order ideal in P. (ii) The maps f ∘ i and f ∘ j are the identity on Q. (iii) The image of i is green, the image of j is red. (iv) For every p ∈ P we have (i ∘ f)(p) ≤ p ≤ (j ∘ f)(p).

(v) The fiber f^{−1} (ˆ0_{Q}) is red except for ˆ0_{P}, the fiber f^{−1} (ˆ1_{Q}) is green except for ˆ1_{P}.

Then the proper part \overline{P}of P is homotopy equivalent to the suspension of the proper part \overline{Q} of Q.

Sketch of proof. Define

g:\{ \begin{matrix}\overline{P} & → & \overline{Q × \{ˆ0, ˆ1\}} , \\ p & ↦ & \{ \begin{matrix}(f(p), ˆ0) & if p is green, \\ (f(p), ˆ1) & if p is red; \end{matrix} \end{matrix}  (1)

and

h:\{ \begin{matrix}\overline{Q × \{ˆ0, ˆ1\}} & → & \overline{P}, \\ (q, ˆ0) & ↦ & i(q), \\ (q, ˆ1) & ↦ & j(q). \end{matrix}  (2)

The assumptions guarantee that the above maps are well-defined and order-preserving. Observe that g ∘ h is the identity map on \overline{Q × \{ˆ0, ˆ1\}} and that \overline{Q × \{ˆ0, ˆ1\}} is homeomorphic to the suspension of \overline{Q}. It is easy to show that both h ∘ g and the identity map on \overline{P} are carried by the following contractible carrier on the order complex Δ(\overline{P}) of \overline{P}.

C : \{ \begin{matrix}Δ(\overline{P}) & → & 2^{Δ(\overline{P})}, \\ σ & ↦ & Δ(P_{≥(i∘f)(minσ)} ∩ P_{≤(j∘f)(maxσ)} ∩ \overline{P}). \end{matrix}

Thus, by the Carrier Lemma [3], the map h ∘ g is homotopic to the identity on \overline{P}, and g and h are homotopy inverses to each other.

We now prove that the assumptions of the Suspension Lemma are satisfied by the following set of data.

P= S(n,d),
Q= S(n − 1,d),
green(S(n,d))= \{ \begin{matrix}\{T ∈ S(n,d): \{n − d,...,n\} ∉ T \} & for d even, \\ \{T ∈ S(n,d): \{n − d,...,n\} ∈ T \} & for d odd; \end{matrix}

red(S(n,d))= \{ \begin{matrix}\{T ∈ S(n,d): \{n − d,...,n\} ∈ T \} & for d even, \\ \{T ∈ S(n,d): \{n − d,...,n\} ∉ T \} & for d odd; \end{matrix}

f : \{ \begin{matrix}S(n,d) & → & S(n − 1,d), \\ T & ↦ & del_{T}(n) ∪ del_{lk_{T}(n)}(n − 1) ∗ \{n − 1\}; \end{matrix}
i:\{ \begin{matrix}S(n − 1,d) & → & S(n,d), \\ T & ↦ & T ∪ stˆ0_{n,d}(n); \end{matrix}

j: \{ \begin{matrix}S(n − 1,d) & → & S(n,d), \\ T & ↦ & del_{T}(n − 1) \\ & & ∪ lk_{T}(n − 1) ∗ \{n\} \\ & & ∪ stˆ1_{n,d}(\{n − 1,n\}). \end{matrix}

Theorem 2.1 shows that S(n,d) is bounded. Moreover, by Theorem 2.2 we know that f(T) is a triangulation of C(n − 1,d) for all triangulations T of C(n,d). The geometric description of f is as follows: starting with the triangulation T of C(n,d), if one slides the vertex n along the moment curve until it coincides with the vertex n − 1, then certain d-simplices of T will degenerate. Removing these degenerate simplices and renaming all occurrences of n by n − 1 yields the triangulation f(T).

The constructions of i and j can be described geometrically as follows: The cyclic polytope C(n − 1,d) can be embedded into the cyclic polytope C(n,d) in many different ways. For example, there is an embedding that sends vertex k of C(n−1,d) to vertex k in C(n,d) for all 1 ≤ k ≤ n − 1. There is another embedding which sends vertex k to vertex k for all 1 ≤ k < n − 1 and vertex n − 1 of C(n − 1,d) to vertex n of C(n,d).

The map i uses the first embedding of C(n−1,d) into C(n,d) to embed a triangulation T of C(n−1,d) into C(n,d). This leads to a partial triangulation of C(n,d). Since the “new” vertex n in C(n,d) “sees” a convex polytope from outside, the only possibility to complete that partial triangulation is to join every facet of T that is “visible” by n to n. It is an easy calculation using Gale’s Evenness Criterion [10, Theorem 0.7] that the given formula for i describes exactly that.

The map j uses the second embedding of C(n−1,d) into C(n,d) for embedding a triangulation T of C(n − 1,d) into C(n,d). Again, the “new” vertex n − 1 “sees” certain facets of a cyclic polytope with n−1 vertices. Given a triangulation of C(n−1,d) that is embedded into C(n,d) in this fashion, the only way to complete it to a triangulation of C(n,d) is to join n−1 with the visible facets of the embedded C(n−1,d). Gale’s Evenness Criterion again allows us to obtain the formula for j. This proves that i and j are well-defined.

In the following we outline the proof of Theorem 1.1 by verifying the assumptions of the Suspension Lemma. Whenever the details are more involved we give a reference to a Lemma in Section 4 or 5, respectively.

If n > d + 2 then ˆ0_{n−1,d} ≠ ˆ1_{n−1,d}. From Lemma 4.1 (resp. 5.1) we get that all maps are order-preserving. From Lemma 4.2 (resp. 5.2) we know that no green element can be above a red one. By construction, f ∘ i and f ∘ j are both the identity on S(n,d). Since whether or not {n−d,...,n} is contained in i(T) (resp. j(T)) does not depend on T, it can easily be seen that the image of i is green and that the image of j is red. From Lemma 4.3 (resp. 5.3) it follows that the preimages of any T ∈ S(n,d) under f are bounded by i(T) and j(T). Finally, Lemma 4.4 (resp. 5.4) imply that ˆ0_{n,d} is the only green element in f^{−1} (ˆ0_{n−1,d}) and that ˆ0_{n,d} is the only red element in f^{−1} (ˆ1_{n−1,d}).

The proof of Theorem 1.1 then follows from the well-known fact that C(d + 2,d) has exactly two triangulations (i. e., its proper part is the empty set which is a (−1)-sphere) and induction on the codimension n − d using the Suspension Lemma 3.1.

4. Lemmas on S_{1}(n,d)

We first formulate a lemma that we are using to establish the comparability of elements in S_{1}(n,d).

Lemma 4.0. Let T and T′ be triangulations of C(n,d). T is less than or equal to T′ in S_{1}(n,d) if and only if there is a triangulation of the region between the characteristic sections of T and T′in C(n,d + 1).

In other words, T ≤_{1} T′if and only if there is a set T̃ of (d + 1)-simplices such that the following hold:

(i) Every pair of (d + 1)-simplices in T are admissible. (ii) For every lower facet S of a (d + 1)-simplex in T̃ either there is another (d + 1)-

simplex in T̃ containing S, or S is in T. (iii) For every upper facet S of a (d + 1)-simplex in T̃ either there is another (d + 1)-

simplex in T̃ containing S, or S is in T′. (iv) Every d-simplex in T \T′is a lower facet of some (d + 1)-simplex in T̃.

(v) Every d-simplex in T′\T is an upper facet of some (d + 1)-simplex in T̃. (vi) Every d-simplex in T \T′∪ T′\T is a facet of at most one (d + 1)-simplex in T̃. If the above assumptions are met we say “T̃ connects T and T′.”

Proof. Given a set of (d + 1)-simplices T̃ as in the assumption we get a sequence of increasing flips from T to T′by sorting the simplices of T̃ by any linear extension of “≺,” as was shown in [5]. On the other hand, every set of (d + 1)-simplices corresponding to a sequence of increasing flips from T to T′has the properties listed above.

We now prove a sequence of lemmas that allows us to apply the Suspension Lemma in the case of S_{1}(n,d). Throughout this section it is always assumed that n > d + 2.

Lemma 4.1. The following maps are order-preserving.

f : \{ \begin{matrix}S_{1}(n,d) & → & S_{1}(n − 1,d), \\ T & ↦ & del_{T}(n) ∪ del_{lk_{T}(n)}(n − 1) ∗ \{n − 1\}; \end{matrix}
i:\{ \begin{matrix}S_{1}(n − 1,d) & → & S_{1}(n,d), \\ T & ↦ & T ∪ stˆ0_{n,d}(n); \end{matrix}

j: \{ \begin{matrix}S_{1}(n − 1,d) & → & S_{1}(n,d), \\ T & ↦ & lk_{T}(n − 1) ∗ \{n\} ∪ stˆ1_{n,d}(\{n − 1,n\}). \end{matrix}

Proof. The assertion for f is contained in Theorem 2.2. To prove the claims about i and j, observe that any increasing flip S̃in T ∈ S_{1}(n − 1,d) gives rise to an increasing flip S̃ in i(T) and an increasing flip S̃\{n − 1} ∪ {n} in j(T). This completes the proof of the lemma.

Lemma 4.2. Let T <_{1} T′∈ S_{1}(n,d) and S_{0} := {n − d,...,n}.

(i) If d is even and S_{0} is in T then S_{0} is also in T′. (ii) If d is odd and S_{0} is in T′then S_{0} is also in T.

Proof. The claim follows from the observation that for even d the simplex S_{0} is an upper facet of C(n,d + 1), whereas for odd d it is a lower facet of C(n,d + 1).

Lemma 4.3. For all T ∈ S_{1}(n,d) we have i(f(T)) ≤_{1} T ≤_{1} j(f(T)).

Proof. We start with a geometric description of the flip sequences that are going to establish the claim. Think of the action of i ∘ f as sliding vertex n of a triangulation T of C(n,d) continuously to n−1 along the edge {n−1,n} and then adding a collection of lower facets of C(n,d +1) to the result. If one imagines this process taking place in C(n,d +1) then one observes that the characteristic section of T slides to the characteristic section of i(f(T)). Every d-simplex S in T that contains n but not n − 1 slides exactly across the (d + 1)- simplex S∪{n−1} (see Figure 3). As the characteristic section T slides, these simplices S are the only ones whose paths sweep out (d + 1)-dimensional simplices. This yields a set of (d + 1)-simplices as in the assumptions of Lemma 4.0.

On the other hand, one may regard the action of j ∘f as sliding vertex n−1 of T continuously to n along the edge {n−1,n} and then adding a bunch of upper facets fo C(n,d +1) to the result. However, the slide—considered in C(n,d +1)—moves the characteristic section of T to the characteristic section of j(f(T)). Again, the “tracks” of certain d-simplices provide the connecting set of (d + 1)-simplices.

T i(f(T)) T  f(T)

Figure 3. The characteristic section of T slides to the characteristic section of f(T). The simplices containing n and not containing n − 1 are sweeping out the increasing flips from i(f(T)) to T.

In the following, we give a combinatorial proof of this idea. For T ∈ S_{1}(n,d) define the following abbreviations.

A(T):= {S ∈ T : n ∈ S,n − 1 ∉ S },
B(T):= {S ∈ T : n ∉ S,n − 1 ∈ S }.

We prove that i(f(T)) ≤_{1} T for an arbitrary T ∈ S_{1}(n,d). Consider the following set of (d + 1)-simplices in C(n,d + 1).

Ã(T) := {S ∪ {n − 1} : S ∈ A(T)}.

We claim that Ã(T) connects i(f(T)) and T. To verify this claim, we check properties (i)-(vi) from Lemma 4.0 in Steps (i)-(vi) below.

Step (i): All pairs of (d + 1)-simplices in Ã(T) are admissible in C(n,d + 1) because any zig-zag-path of length d + 3 can be transformed into a zig-zag-path of length (d + 2) by deleting n; deleting n from a simplex in Ã(T), however gives a simplex in f(T); all of these are clearly admissible in C(n − 1,d).

Step (ii): We now show that every lower facet S of a (d + 1)-simplex S̃in Ã(T) is either in i(f(T)) or there is another (d + 1)-simplex S̃in Ã(T) containing S.

To this end, let S be an arbitrary lower facet of a (d + 1)-simplex S̃in T̃. Hence, S̃\S is an even gap of S in S̃.

Case 1: If S̃\S = n then S is contained in f(T), in particular it is contained in i(f(T)). Case 2: If S̃\S = s < n − 1 then F := S\{n − 1} is a (d − 1)-simplex in T. If F is a facet of C(n,d) then it is an upper facet of C(n,d) because n − 1 is an odd

gap in F. Then S = F ∪ {n − 1} was already a lower facet of C(n,d + 1) containing n and n − 1. However, all these lower facets of C(n,d + 1) are in i(f(T)) by construction, and thus S ∈ i(f(T)).

If F is not a facet of C(n,d) then there is another simplex S′∈ T with S′≠ S and F ⊂ S′. Since n − 1 ∉ S′we have that S̃′:= S′∪ {n − 1} ∈ Ã(T) with S̃′≠ S̃and S ⊂ S̃′.

Step (iii): Next, we show that every upper facet S of a (d +1)-simplex S̃in Ã(T) is either in T or there is another (d + 1)-simplex S̃in Ã(T) containing S.

To see this, let S be an arbitrary upper facet of a (d + 1)-simplex S̃in T̃. Hence, S̃\S is an odd gap of S in S̃.

Case 1: If S̃\S = n − 1 then S is contained in T by the definition of Ã(T).

Case 2: If S̃\S = s < n − 1 then F := S\{n − 1} is a (d − 1)-simplex in T.

We show now that F is not a facet of C(n,d): Because s is an odd gap of S in S̃ and n − 1 > s is an additional gap of F larger than s we conclude that s is an even gap of F in S̃. However, n − 1 is clearly an odd gap of F in S̃because n ∈ F. Thus, F contains an even and an odd gap, and is therefore not a facet of S̃. Consequently, it cannot be a facet of C(n,d).

Hence, there is another simplex S′∈ T with S′≠ S and F ⊂ S′. Since n−1 ∉ S′we have that S̃′:= S′∪ {n − 1} ∈ Ã(T) with S̃′≠ S̃and S ⊂ S̃′.

Step (iv): We now prove that every d-simplex in i(f(T))\T is a lower facet of some (d + 1)-simplex S̃in Ã(T).

Let S be a d-simplex in i(f(T)) but not in T. There are two types of d-simplices in i(f(T))\T: simplices of the form S = S′\{n} ∪ {n − 1} with S′∈ A(T) (case 1), and lower facets of C(n,d + 1) containing n and n − 1 (case 2) .

Case 1: If S is of the form S = S′\{n} ∪ {n − 1} with S′∈ A(T) then S̃:= S ∪ {n} is in Ã(T), and n is clearly an even gap of S in S̃. Thus, S is a lower facet of the simplex S̃∈ Ã(T).

Case 2: If S is a lower facet of C(n,d + 1) containing n and n − 1 then all gaps of S are even. Hence, all gaps of F := S\{n−1} are odd. Thus, F is an upper facet of C(n,d). This leads to the existence of a d-simplex S′in T containing F. Since n is in F we know that n is also in S′. If n − 1 ∈ S′then S = S′∈ T; contradiction to S ∈ i(f(T))\T. Therefore, S′is in A(T) and, consequently, S̃:= S′∪ {n − 1} is a (d + 1)-simplex in Ã(T). Moreover, S = F ∪ {n − 1} is a facet of S̃ because S̃ contains n − 1. Additionally, S is — by the assumption of this case — a lower facet of C(n,d + 1), so it must be a lower facet of S̃.

Step (v): We now prove that every d-simplex in T \i(f(T)) is an upper facet of some (d + 1)-simplex S̃in Ã(T).

Let S be a d-simplex in T but not in i(f(T)). Then S is, in particular, not contained in f(T). There are two types of d-simplices in T \f(T): simplices from A(T) (case 1), and simplices containing both n − 1 and n (case 2).

Case 1: Assume S is in A(T). Then S̃:= S ∪ {n − 1} is in Ã(T). Since n − 1 is an odd gap of S in S̃we conclude that S is an upper facet of the (d + 1)-simplex S̃in Ã(T).

Case 2: If both n−1 and n are in S then S cannot be a lower facet of C(n,d +1), because all lower facets of C(n,d + 1) containing both n and n − 1 are in i(f(T)) by construction. Assume, for the sake of contradiction, that F := S\{n−1} is a facet of C(n,d). Then either all gaps of F are even or all gaps of F are odd. Since n ∈ F we know that n − 1 is an odd gap of F, thus all gaps of F must be odd. However, then all gaps of S = F ∪ {n − 1} are even; contradiction to the fact that S is not a lower facet of C(n,d +1). We conclude that F is not a facet of C(n,d). Thus, there is another simplex S′≠ S in T containing F. Moreover, because n − 1 ∉ S′but n ∈ S′, we have S′∈ A(T), and, consequently, S̃:= S′∪ {n − 1} is in Ã(T). Because n − 1 is an odd gap of S′in S̃we know that S′is an upper facet of S̃. Moreover, since S′and S are both in T they are admissible in C(n,d). That means that S is also an upper facet of S̃. (A lower and an upper facet of a (d + 1)-simplex in C(n,d + 1) are never admissible in C(n,d).)

Step (vi): Finally we prove that every simplex in T \i(f(T)) ∪ i(f(T))\T is a facet of at most one (d + 1)-simplex in Ã(T).

Case 1: S is a d-simplex in T \i(f(T)). If S is in A(T) then S̃= S ∪ {n − 1} is the only (d + 1)-simplex in Ã(T) containing S because membership in Ã(T) requires the containment of n−1. If both n and n−1 are in S then we proceed as follows. Assume, for the sake of contradiction, that there are two distinct (d +1)-simplices S̃and S̃′in Ã(T) containing S. Then S is a lower facet of one of them, say S̃and an upper facet of the other one, say S̃′. In other words, s:= S̃\S̃′< n−1 is an odd gap of S̃′and s′:= S̃′\S̃< n−1 is an even gap of S̃ in S̃∪ S̃′. By construction of Ã(T), we know that S̃= R ∪ {n − 1} and S̃′= R′∪ {n − 1} for some R,R′∈ A(T). In particular, R and R′are in T, thus admissible in C(n,d). However, R = S̃\{n − 1} and R′= S̃′\{n − 1}. Therefore, s is an even gap of R′and s′is an odd gap of R in R ∪ R′. But that means, R′is a lower and R is an upper facet of the (d + 1)-simplex R ∪ R′; contradiction to the fact that R and R′are admissible in C(n,d).

Case 2: S is a d-simplex in i(f(T))\T. If S is of the form S′\{n}∪{n−1} for some S′∈ A(T) then S∪{n} is the only (d +1)-simplex in Ã(T) containing S because membership in Ã(T) requires the containment of n. On the other hand, if S is a lower facet of C(n,d + 1) then there cannot be two distinct (d +1)-simplices which both contain S and are admissible in C(n,d + 1).

Steps 1 to 6 prove that the assumptions of Lemma 4.0 are satisfied, thus Ã(T) connects i(f(T)) and T, proving i(f(T)) ≤_{1} T.

Analogously, the set

B̃(T) := { S̃∪ {n} : S ∈ B(T)}.

connects T and j(f(T)), proving T ≤_{1} j(f(T)). We omit the details verifying this, which are similarly tedious.

Lemma 4.4. Let T be in S_{1}(n,d) and S_{0} := {n − d,...,n}.

(i) Let d be even, f(T) = ˆ0_{n−1,d}, and S_{0} ∉ T. Then T = ˆ0_{n,d}. (ii) Let d be even, f(T) = ˆ1_{n−1,d}, and S_{0} ∈ T. Then T = ˆ1_{n,d}. (iii) Let d be odd, f(T) = ˆ0_{n−1,d}, and S_{0} ∈ T. Then T = ˆ0_{n,d}. (iv) Let d be odd, f(T) = ˆ1_{n−1,d}, and S_{0} ∉ T. Then T = ˆ1_{n,d}.

Proof. For the proof of (i), let T ∈ S_{1}(n,d) for even d with f(T) = ˆ0_{n−1,d}. Assume that T ≠ ˆ0_{n,d}. Recall that any such element T in S_{1}(n,d) can be connected to ˆ0_{n,d} by a sequence of decreasing flips (see Theorem 2.1). The map f is order-preserving (see Theorem 2.2); thus every element in such a sequence is mapped by f to ˆ0_{n−1,d}. Because of Lemma 4.2, we may therefore assume that T differs from ˆ0_{n,d} by exactly one increasing flip corresponding to a (d + 1)-simplex S̃. The simplex S̃must contain both n − 1 and n because otherwise it would give rise to a (non-trivial) flip from ˆ0_{n−1,d} to f(T) in contradiction to f(T) = ˆ0_{n−1,d}. The only flip in ˆ0_{n,d} containing n − 1 and n corresponds, however, to the (d + 1)-simplex S̃= {1,n − d,...,n}. The fact that S_{0} is an upper facet of S̃, thus is contained in the triangulation resulting from this flip, gives a contradiction. Thus, claim (i) is proved.

The proofs of the remaining statements are analogous with

S̃= \{ \begin{matrix}\{n − d − 1,n − d,...,n\} & decreasing flip in ˆ1_{n,d} for (ii), \\ \{n − d − 1,n − d,...,n\} & increasing flip in ˆ0_{n,d} for (iii), \\ \{1,n − d,...,n\} & decreasing flip in ˆ1_{n,d} for (iv). \end{matrix}

5. Lemmas for S_{2}(n,d)

This section is devoted to proving an analogous set of lemmas to the ones in the previous section, in order to guarantee the assumptions of the Suspension Lemma for S_{2}(n,d). Again, in the following n > d + 2.

Lemma 5.1. The following maps are order-preserving.

f : \{ \begin{matrix}S_{2}(n,d) & → & S_{2}(n − 1,d), \\ T & ↦ & T \n:= del_{T}(n) ∪ del_{lk_{T}(n)}(n − 1) ∗ \{n − 1\}; \end{matrix}
i:\{ \begin{matrix}S_{2}(n − 1,d) & → & S_{2}(n,d), \\ T & ↦ & T ∪ stˆ0_{n,d}(n); \end{matrix}

j: \{ \begin{matrix}S_{2}(n − 1,d) & → & S_{2}(n,d), \\ T & ↦ & lk_{T}(n − 1) ∗ \{n\} ∪ stˆ1_{n,d}(\{n − 1,n\}). \end{matrix}

Proof. That i and j are order-preserving is easily seen by considering the following facts: both maps embed a triangulation of C(n − 1,d) into C(n,d); i copies the original triangulation, j renames n − 1 to n. This does not change any height relations of piecewise linear sections to each other. Then both maps add a set of simplices which does not depend upon T. These are consequently at the same height for all triangulations. Thus, all height relations are maintained.

We now prove the assertion concerning f. We use the fact that the map f : S(n,d) → S(n − 1,d) has the following geometric interpretation: given a triangulation T of C(n,d), imagine a homotopy that “slides” the vertex n down the moment curve toward the vertex n − 1, so that at t = 0 one has the triangulation T (0) = T of the original cyclic polytope C(n,d), and at t = 1 some of the simplices of T (1) (namely those containing both n − 1 and n) have become degenerate (volume zero). If one eliminates these degenerate simplices from T (1) and relabels the vertex n by n − 1 in the remaining simplices, one obtains the triangulation f(T) of C(n − 1,d).

To prove that f is order-preserving, assume T ≤_{2} T′, and we will show that f(T) ≤_{2} f(T′). Fix a point x ∈ C(n−1,d), and for 0 ≤ t ≤ 1, let T (t)(x)_{d+1} ,T′(t)(x)_{d+1} be the (d + 1)^{st}-coordinates of the image of x under the parametrized characteristic sections T (t),T′(t) : C(n,d) → C(n,d + 1). Since T ≤_{2} T′, we have

T′(t)(x)_{d+1} − T (t)(x)_{d+1} ≥ 0 for 0 ≤ t < 1.

However T′(t)(x)_{d+1} − T (t)(x)_{d+1} is clearly a continuous function of t, so the same inequality holds for t = 1. Hence

f(T)(x)_{d+1} = T (1)(x)_{d+1} ≤ T′(1)(x)_{d+1} = f(T′)(x)_{d+1}

which shows that f(T) ≤_{2} f(T′)

Lemma 5.2. Let T < T′∈ S_{2}(n,d) and S_{0} := (n − d,...,n).

(i) If d is even and S_{0} is in T then S_{0} is also in T′. (ii) If d is odd and S_{0} is in T′then S_{0} is also in T.

Proof. The assertion follows from exactly the same argument as given in the proof of Lemma 4.2.

Lemma 5.3. For all T ∈ S_{2}(n,d) we have i(f(T)) ≤_{2} T ≤_{2} j(f(T)).

Proof. This follows from Lemma 4.3 and the fact that T ≤_{1} T′ always implies T ≤_{2} T′ (see [4]).

Lemma 5.4. Let T be in S_{2}(n,d) and S_{0} := {n − d,...,n}.

(i) Let d be even, f(T) = ˆ0_{n−1,d}, and S_{0} ∉ T. Then T = ˆ0_{n,d}. (ii) Let d be even, f(T) = ˆ1_{n−1,d}, and S_{0} ∈ T. Then T = ˆ1_{n,d}. (iii) Let d be odd, f(T) = ˆ0_{n−1,d}, and S_{0} ∈ T. Then T = ˆ0_{n,d}. (iv) Let d be odd, f(T) = ˆ1_{n−1,d}, and S_{0} ∉ T. Then T = ˆ1_{n,d}.

Proof. This statement is independent of the partial order S_{1}(n,d) or S_{2}(n,d) under consideration. Thus the proof of Lemma 4.4 is valid here as well.

6. The Generalized Baues Problem for C(n,d) with d ≤ 3

The goal of this section is to prove a new special case of the generalized Baues problem, but we must first recall the definition of the Baues poset Baues(C(n,d)). A polytopal decomposition δ of C(n,d) is a collection {V_{α}} of vertex subsets V_{α} ⊆ [n] satisfying

• For all α, |V_{α}| ≥ d + 1.

• Any two cyclic subpolytopes C(V_{α},d),C(V_{β},d) intersect in a common face (possibly empty).

• The union of the cyclic subpolytopes C(V_{α},d) covers C(n,d), i. e.,

⋃_{α} C(V_{α},d) = C(n,d)

Say that a polytopal decomposition is proper if it is not the trivial decomposition {[n]}.

The Baues poset Baues(C(n,d)) is the set of all proper polytopal decompositions ordered by refinement, i. e., δ = {V_{α}} ≤ δ′= {V_{α′}} if for every V_{α} ∈ δ there exists a V_{α′} ∈ δ′ with V_{α} ⊆ V_{α′}. One can check that this agrees with the poset considered in the Generalized Baues Problem [1] for the case of subdivisions of a cyclic polytope. Theorem 1.2 now reads as follows.

Theorem 6.1. For d ≤ 3 the poset Baues(C(n,d)) is homotopy equivalent to a sphere of dimension n − d − 2.

As was said in the introduction, our method will be to show that Baues(C(n,d)) is homotopy equivalent to the suspension susp(\overline{S_{2}(n,d)}). We begin by defining a map ϕ from Baues(C(n,d)) to intervals in S_{2}(n,d). An element δ of Baues(C(n,d)) is a polytopal subdivision of C(n,d), so let ϕ(δ) be the set of all triangulations of C(n,d) which refine it.

Lemma 6.2. For any δ in Baues(C(n,d)), • the set ϕ(δ) is a non-empty interval in S_{2}(n,d).

• ϕ(δ) is not the improper interval consisting of all S_{2}(n,d).

• δ ≤ δ′in Baues(C(n,d)) implies ϕ(δ) ⊆ ϕ(δ′).

• ϕ is injective, i. e., ϕ(δ) = ϕ(δ′) implies δ = δ′.

Proof. Since δ is a polytopal subdivision of C(n,d), and subsets V of the vertices of C(n,d) span cyclic subpolytopes C(V,d), we know that δ gives a decomposition

C(n,d) = ⋃_{α} C(V_{α},d)

for some vertex sets V_{α} in which the C(V_{α},d) all have disjoint interiors. If we let ˆ0_{α}, ˆ1_{α} denote the bottom and top triangulations of C(V_{α},d), then one can form two triangulations T and T′respectively, by refining δ according to ˆ0_{α} and ˆ1_{α} respectively on each subpolytope C(V_{α},d). It is then clear from the definition of S_{2}(n,d) that ϕ(δ) = [T,T′]. This proves the first assertion of the lemma.

To prove the second assertion, note that since δ is a non-trivial polytopal subdivision of C(n,d), it must use at least one (d − 1)-simplex σ spanned by the vertices of C(n,d) which lies interior to C(n,d), and therefore this simplex σ would lie in every triangulation in ϕ(δ). If ϕ(δ) were all of S_{2}(n,d), then in particular this would imply that the bottom and top triangulations ˆ0, ˆ1 have this simplex σ in common. But one can easily check from the explicit description of the triangulations ˆ0, ˆ1 given in [4] or [5] that they have no interior (d − 1)-simplices in common.

To see the third assertion, note δ ≤ δ′means that δ refines δ′as a polytopal subdivision, so any triangulation T which refines δ will also refine δ′, and hence ϕ(δ) ⊆ ϕ(δ′).

To see the fourth assertion, it suffices to show that δ is completely determined by ϕ(δ), in the sense that the set of (d − 1)-simplices of δ is the intersection of all the sets of (d − 1)-simplices of its triangulation refinements. Certainly the (d − 1)-simplices of δ are contained in this intersection. This intersection cannot be larger because for each α, (using the notation of the first paragraph), the two triangulations ˆ0_{α}, ˆ1_{α} share no common (d − 1)-simplices interior to C(V_{α},d).

We next recall and introduce some notions about lattices. Given a lattice L with bottom and top elements ˆ0, ˆ1, an element of L which covers ˆ0 (resp. is covered by ˆ1) is called an atom (coatom), resp. The lattice L is atomic (resp. coatomic) if the join of all the atoms is ˆ1 (resp. the meet of all the coatoms is ˆ0). Any interval [x,y] in a lattice is a lattice itself, and will be called atomic or coatomic if it satisfies the previous conditions. An interval [x,y] will be called proper if it is not the whole lattice L = [ˆ0, ˆ1]. Recall that the proper part of L is the subposet \overline{L}:= L\\{ˆ0, ˆ1\}.

We now define three interval posets as certain collections of intervals in L ordered by inclusion of intervals:

• Int(L) — all non-empty intervals in L,

• \overline{Int}(L) — all non-empty, proper intervals in L,

• \overline{Int}_{atomic}(L) — all non-empty, proper, atomic intervals in L. Similarly one can define \overline{Int}_{coatomic}(L).

In [9] it was shown that Int(L) is canonically homeomorphic to L, and that \overline{Int}(L) is canonically homeomorphic to susp(\overline{L}), i. e., the suspension of the proper part of L. One can view Lemma 6.4 below as asserting an analogous statement, up to homotopy, for \overline{Int}_{atomic}(L).

We recall (Theorem 2.5) that for d ≤ 3 S_{2}(n,d) is a lattice, and note that Lemma 6.2 shows that ϕ defines an injective, order-preserving map Baues(C(n,d)) → \overline{Int}(S_{2}(n,d)).

Lemma 6.3. For d ≤ 3, the image of ϕ: Baues(C(n,d)) → \overline{Int}S_{2}(n,d) is exactly

\overline{Int}_{coatomic}(S_{2}(n,d)).

Proof. To see that ϕ(δ) is always a coatomic interval in S_{2}(n,d), we use the notation from the proof of Lemma 6.2, and note the following isomorphism of posets:

ϕ(δ) = [T,T′] ≅ ∏_{α} [ˆ0_{α}, ˆ1_{α}].

Since each interval [ˆ0_{α}, ˆ1_{α}] is isomorphic to S_{2}(n′,d) for some n′< n, the coatomicity of ϕ(δ) would follow if we knew that S_{2}(n,d) is a coatomic lattice for d ≤ 3. But if S_{2}(n,d) were not coatomic then its proper part \overline{S_{2}(n,d)}would be contractible (see, e. g.,[3, Theorem 10.14]), contradicting Theorem 2.6 above.

It remains then to show that every coatomic interval in S_{2}(n,d) is of the form ϕ(δ) for some δ in Baues(C(n,d)). For d = 1, this is trivial since the cyclic polytope C(n,1) is simply a line segment with n − 2 interior subdivision points. Triangulations of C(n,1) are specified by their subset of interior vertices and S_{2}(n,d) is a Boolean algebra B_{n−2} , so that every interval is coatomic, and it is easy to see that every interval is ϕ(δ) for some δ in Baues(C(n,d)).

For d = 2,3 the fact that every coatomic interval in S_{2}(n,d) is of the form ϕ(δ) requires some argument. Assume we have such a coatomic interval [T,T′], and we will show how to construct its preimage δ. Form a graph G whose vertices are the d-simplices σ in the triangulation T′, and whose edges correspond to a pair of d-simplices σ,σ′which share a (d −1)-simplex τ that is not a simplex in T. Let {G_{α}} be the various connected components of G, and define V_{α} to be the set of all vertices of C(n,d) which lie in a simplex of G_{α}. We wish to prove two claims about these graphs:

• If σ,σ′are simplices of T′which correspond to an edge of G, then their union is a cyclic subpolytope C(d + 2,d) which supports a bistellar operation corresponding to a covering relation between T′and some coatom of the interval [T,T′].

• For each α, the connected component G_{α} is a path, and the set of d-simplices σ corresponding to G_{α} gives exactly the maximal simplices of the top triangulation ˆ1_{α} of the cyclic subpolytope C(V_{α},d).

Assuming these two claims for the moment, we show how to finish the proof. The second claim implies that the decomposition C(n,d) = ⋃ _{α} C(V_{α},d) defines a polytopal subdivision δ. Furthermore, as in the first paragraph of this proof, we know that ϕ(δ) is equal to some coatomic interval [T_{δ},T′_{δ}], where T,T′refine δ and the restriction to C(V_{α},d) of T,T′looks like ˆ0_{α}, ˆ1_{α} respectively. By the second claim, this means that T′= T′_{δ}. By both claims together, every coatom of the interval [T_{δ},T′_{δ}] is also a coatom of [T,T′] (i. e., all of the former coatoms lie above T), and hence by coatomicity of [T,T′] we must have T = T_{δ}. Therefore [T,T′] = ϕ(δ) as desired.

To show the first claim, assume σ,σ′are simplices of T′which correspond to an edge of G, so there intersection is a (d − 1)-simplex τ which is not in T. Assume for the sake of contradiction that the union σ ∪ σ′does not support a bistellar operation as asserted in the claim. Then every coatom T ′′of [T,T′] will have τ in its submersion set sub_{⌈ \frac{d}{2}⌉}(T ′′) (see Proposition 2.3). Since the meet operation in S_{2}(n,d) corresponds to intersection of submersion sets, coatomicity of [T,T′] implies that sub_{⌈ \frac{d}{2}⌉}(T) would also contain τ. But then the fact that τ is not a (d − 1)-simplex of T would imply that

• if d = 2 then τ = \{i,j\} must be “foiled” by some other τ′= \{k,l\} in sub_{⌈ \frac{d}{2}⌉}(T) which satisfies i < k < j < l (see Proposition 2.4).

• if d = 3 then τ = {i,j,k} must be “foiled” by one of its edges, say {i,j}, intertwining another triple τ′= \{x,y,z\} in sub_{⌈ \frac{d}{2}⌉}(T) in the sense that x < i < y < j < z (see Proposition 2.4)

However in both of these cases, τ′would also lie in sub_{⌈ \frac{d}{2}⌉}(T′) since T < T′in S_{2}(n,d), and hence would “foil” τ from being a (d − 1)-simplex of T′. Contradiction.

To show the second claim, note that the first claim implies very stringent requirements on what σ,σ′can look like whenever they correspond to an edge in G:

• if d = 2, σ = {i,j,l},σ′= {j,k,l} for some i < j < k < l, and

• if d = 3, σ = {i,j,k,m},σ′= {i,k,l,m} for some i < j < k < l < m. It is easy to check that these requirements, combined with the fact that a (d − 1)-simplex τ can lie in at most two d-simplices of T′, implies that the degree of any vertex in a connected component G_{α} can be at most 2. In fact, G_{α} is constrained to look like the following path of d-simplices:

• for d = 2,

{v_{1}v_{2}v_{r}},{v_{2}v_{3}v_{r}},{v_{3}v_{4}v_{r}},... ,{v_{r−2} v_{r−1} v_{r}}

• for d = 3,

{v_{1}v_{2}v_{3}v_{r}},{v_{1}v_{3}v_{4}v_{r}},{v_{1}v_{4}v_{5}v_{r}},... ,{v_{1}v_{r−2} v_{r−1} v_{r}}

where v_{1} < ···< v_{r} are the vertices V_{α} of G_{α} written increasing order. In both cases this description matches exactly the top triangulation ˆ1_{α} of C(V_{α},d).

Once the image of ϕ has been established, Theorem 6.1 follows by combining

• Lemma 6.4 below,

• the above-mentioned fact that the proper interval poset \overline{Int}(L) is homeomorphic to susp(\overline{L}), and

• Theorem 2.6 or Theorem 1.1.

Lemma 6.4. Let L be any finite lattice. Then \overline{Int}_{atomic}(L) (or \overline{Int}_{coatomic}(L)) is homotopy equivalent to \overline{Int}(L).

Lemma 6.4 follows from a more general lemma, which we think is of independent interest. We are indebted to P. Webb for the statement and proof of this lemma.

Lemma 6.5. Let P be a poset with ˆ0, ˆ1. If {[x_{i},y_{i}]}_{i=1}^{r} is any finite collection of intervals with the open intervals (x_{i},y_{i}) contractible for all i, then the inclusion

\overline{Int}P\\{[x_{i},y_{i}]\}_{i=1}^{r} ↪ \overline{Int}P

induces a homotopy equivalence.

Lemma 6.4 then follows from Lemma 6.5 by letting P = L and letting {[x_{i},y_{i}]}_{i=1}^{r} be the non-coatomic intervals of L. These non-coatomic intervals satisfy the hypothesis of the lemma by [3, Theorem 10.14].

Lemma 6.5 follows immediately from the following two sublemmas:

Sublemma 6.6. [2] In a poset Q, if {q_{i}}_{i=1}^{r} is a finite subset with Q_{<q_{i}} contractible for all i, then the inclusion

Q\{q_{i}}_{i=1}^{r} ↪ Q

induces a homotopy equivalence.

Proof. Re-index the elements {q_{i}}_{i=1}^{r} in such a way that q_{i} > q_{j} in Q implies i < j. Then

(Q\{q_{1},... ,q_{i−1} })_{<q_{i}} = Q_{<q_{i}}

is contractible for all i, so an application of Quillen’s Fiber Lemma [3, Theorem 10.5] proves the homotopy equivalence by induction on i.

We can apply Sublemma 6.6 with Q = \overline{Int}P to prove Lemma 6.5 once we have established

Sublemma 6.7. In a poset P with ˆ0, ˆ1, if an open interval (x,y) is contractible, then (\overline{Int}P)_{<[x,y]} is contractible.

Proof. Note that

(\overline{Int}P)_{<[x,y]}= \overline{Int}[x,y].

But \overline{Int}[x,y] is homeomorphic to the suspension susp(x,y) by [9], and hence contractible since (x,y) was assumed contractible.

7. Open Problems

The following are some remarks and remaining open problems about triangulations of cyclic polytopes which we consider interesting.

1. The proof of Theorem 6.1 relied heavily on the fact established in [4] that S_{2}(n,d) is a lattice for d ≤ 3. Unfortunately, computer calculations have shown that S_{2}(9,4) and S_{2}(10,5) are not lattices, rendering this lattice-theoretic method of proof invalid for d ≥ 4 (and resolving negatively Conjecture 2.13 of [4]). However we would still conjecture the following:

Conjecture 7.1. The image of ϕ : Baues(C(n,d)) → \overline{Int}S_{2}(n,d) is exactly the subposet consisting of those closed intervals in S_{2}(n,d) whose open interval is not contractible.

As in Section 6, this conjecture would resolve in the affirmative the Baues problem for triangulations of all cyclic polytopes. It is easy to see that one direction in this conjecture is true, namely that any interval in the image of ϕ is isomorphic to a Cartesian product of posets isomorphic to S_{2}(n_{α},d) for various n_{α}, and hence has proper part homotopy equivalent to a sphere. Consequently, the above conjecture also has as a corollary the calculation of the homotopy type and Möbius function for all (open) intervals in S_{2}(n,d).

2. Do the partial orders S_{1}(n,d),S_{2}(n,d) coincide?

8. Acknowledgments

The authors thank P. Webb for pointing out Lemma 6.5, which gives an easier and more conceptual proof than their original proof of Lemma 6.4.

References

[1] L. J. Billera, M. M. Kapranov, and B. Sturmfels, Cellular strings on polytopes, Proceedings of the American Mathematical Society 122 (1994), 549–555.

[2] S. Bouc, Homologie de certains ensembles ordonnés, C. R. Acad. Sci. Paris Sér I, 299 (1984), 49–52.

[3] A. Björner, Topological methods, Handbook of Combinatorics (R. Graham, M. Grötschel, and L. Lovász, eds.), North Holland, Amsterdam, 1995, pp. 1819–1872.

[4] P. H. Edelman and V. Reiner, The higher Stasheff-Tamari posets, Mathematika 43 (1996), 127–154.

[5] J. Rambau, Triangulations of cyclic polytopes and higher Bruhat orders, Preprint No. 496/1996, Fachbereich Mathematik, TU-Berlin, Mathematika, to appear.

[6] J. Rambau, Polyhedral subdivisions and projections of polytopes, Ph.D. Thesis, Fachbereich Mathematik, TU-Berlin, Shaker-Verlag, Aachen, 1996.

[7] J. Rambau, A suspension lemma for bounded posets, Manuscript 1997.

[8] J. Rambau and G. M. Ziegler, Projections of polytopes and the Generalized Baues Conjecture, Discrete & Computational Geometry, 16 (1996), 215–237.

[9] J. W. Walker, Topology and combinatorics of ordered sets, Ph.D. Thesis, MIT, 1981.

[10] G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, Berlin, 1994.

Paul H. Edelman, School of Mathematics, University of Minnesota, Minneapolis MN 55455

 E-mail address: edelman@math.umn.edu

Jörg Rambau, Konrad-Zuse-Zentrum für Informationstechnik, Takustr. 7, 14195 Berlin, Germany

E-mail address: rambau@zib.de

Victor Reiner, School of Mathematics, University of Minnesota, Minneapolis MN 55455

 E-mail address: reiner@math.umn.edu