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

   
Order Theory

Triangulations of a convex $n$-gon have been studied from a purely combinatorial point of view for quite a long time. Starting in 1962, TAMARI [72] investigated the poset $\mathcal{T}_n$of all complete binary bracketings of a string of length $n-1$. Its elements turned out to be in one-to-one correspondence with the triangulations of a convex $n$-gon without new vertices. Moreover, the covering relations in $\mathcal{T}_n$ correspond to edge-flipping operations that have a certain direction.

Definition 1.2.6   Let $T_n$ be the set of all complete binary bracketings of a string $S$ of length $n-1$. Define

$$\bigl((AB)C\bigr) < \bigl(A(BC)\bigr) \quad \text{for substrings $A, B, C$\space of $S$ }.$$

Then the transitive closure of ``$<$'' defines a partial order ``$\le$'' on $T_n$. In view of Theorem 1.2.7 below, the poset $(T_n, \le)$ is called the   Tamari lattice  $\mathcal{T}_n$.

Theorem 1.2.7   (HUANG & TAMARI [36]) $\mathcal{T}_n$ is a lattice.

The covering relations in $\mathcal{T}_n$ can also be considered as directed   rotations in binary trees, giving a link to computer science. The geometric connection is as follows.

Lemma 1.2.8   $\mathcal{T}_n$ is isomorphic to the set of all   triangulations of the $n$-gon $Q_n$ where the vertices $1, \dots , n$ are ordered counter-clockwise. A covering relation in $\mathcal{T}_n$ corresponds to an edge-flipping operation in a quadrangle $(i,j,k,l)$ with $i < k < j < l$ that replaces the diagonal $(i,j)$ with $(k,l)$.

The diameter of the Hasse diagram of $\mathcal{T}_n$ is just the edge-flipping diameter of $Q_n$, and thus the bounds by SLEATOR, TARJAN & THURSTON [67] (see the previous section) apply to  $\mathcal{T}_n$. Additionally, PALLO [59] found an $O(n^{3/2})$-algorithm to explicitly compute the distance of two elements of  $\mathcal{T}_n$.

The secondary polytope for this special case was found independently by HAIMAN [33] and LEE [42] before the general theory of secondary polytopes was developed by GELFAND, KAPRANOV & ZELEVINSKY [28].

Theorem 1.2.9   (HAIMAN [33], LEE [42], also MILNOR [52]) The Hasse diagram of $\mathcal{T}_n$ is the edge graph of an $(n-3)$-polytope, the associahedron.

Using methods of formal concept analysis, GEYER [31] found some more involved order theoretic facts about  $\mathcal{T}_n$. We omit them here because the corresponding notions have no obvious connection to the geometry of triangulations.

The paper by EDELMAN & REINER [21], which we already mentioned at the end of Section 1.1(a), presents a natural geometric generalization of $\mathcal{T}_n$. There are   increasing bistellar operations for   triangulations of the   cyclic polytope $C(n,d)$, which coincide in the special case $d = 2$ with the directed edge-flipping operations (see Section 3.5 for a detailed discussion). This yields a partial order on the set of all triangulations of $C(n,d)$, the   (first) higher Stasheff-Tamari order $\mathcal{S}_1(n,d)$.

Our positive result in Chapter 3 shows that at least the boundedness of $\mathcal{T}_n$ survives in $\mathcal{S}_1(n,d)$. Moreover, the correspondence between equivalence classes of maximal chains in $\mathcal{S}_1(n,d-1)$ and elements in $\mathcal{S}_1(n,d)$(see Theorem 1.1.18) yields an additional order theoretic structure. The same property holds for the   higher Bruhat order $\mathcal{B}(m,k)$of MANIN & SCHECHTMAN [48], further studied by ZIEGLER [74]. A connection between these two classes of posets was first detected by KAPRANOV & VOEVODSKY [40]; it will be an object of intensive study in Section 3.8 of this thesis.