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

   
Oriented Matroid Theory

The framework of oriented matroids is by now a well-developed tool to study various kinds of combinatorial problems. At the same time, it has become a source of problems that are interesting in their own right. We sketch the connnection between the unsolved Extension Space Conjecture and the Generalized Baues Conjecture, which is provided by the   Bohne-Dress Theorem.

Definition 1.2.10   The   extension poset of an oriented matroid  $\mathcal{M}$ is the set $\mathcal{E}(\mathcal{M})$ of all extensions of  $\mathcal{M}$, partially ordered by the weak map relation. The   order complex $\Delta\mathcal{E}(\mathcal{M})$ of $\mathcal{E}(\mathcal{M})$ is called the   extension space of  $\mathcal{M}$.

 

Conjecture 1.2.11 (Extension Space Conjecture)   Let $\mathcal{M}$ be a realizable oriented matroid of rank $d$ on $n$ points. Then $\Delta\mathcal{E}(\mathcal{M})$ has the homotopy type of a $(d-1)$-sphere.

That the realizability assumption is essential was shown by MNËV & RICHTER-GEBERT [53]. They constructed oriented matroids with even disconnected extension spaces. Their result ``killed'' an older ``extension space conjecture'' that did not assume realizability.

STURMFELS & ZIEGLER [71] derived affirmative answers to the extension space conjecture for   strongly euclidean oriented matroids, in particular for $d \le 3$, for $n \le d + 2$, and for the   alternating oriented matroid $\mathcal{Z}(n,d)$. The latter example is the oriented matroid of the vector configuration of homogenous coordinates of the vertices of the standard cyclic polytope $C(n,d)$.

Definition 1.2.12   A   zonotope is a polytope $Z \subset \mathbb{R} ^d$ that is the projection of a hypercube, or, equivalently, the Minkowski sum of finitely many line segments $[-v_i, +v_i] \subset \mathbb{R} ^d$, where $V := \{ v_1, \dots , v_n \}$ is a configuration of vectors in $\mathbb{R} ^d$. The   oriented matroid $\mathcal{M}(Z)$ of $Z$ is defined as the oriented matroid of $V$. This oriented matroid has rank $\dim (V)$.

Definition 1.2.13   Let $Z$ be a zonotope. A   (weak) zonotopal tiling of $Z$ is a collection $\mathcal{Z}$ of zonotopes that forms a polyhedral subdivision of $Z$.

A new proof of the following theorem may be found in RICHTER-GEBERT & ZIEGLER [64].

 

Theorem 1.2.14 (Bohne-Dress Theorem)   (BOHNE [16]) Let $Z$ be a zonotope given by a vector configuration $V \subset \mathbb{R} ^d$. There is a one-to-one correspondence between the set of all zonotopal tilings $\mathcal{Z}$ of $Z$ and the oriented matroid liftings $\widehat{\mathcal{M}}(Z)$ of $\mathcal{M}(Z)$.

Figure 1.9 shows a zonotopal tiling corresponding to the non-realizable oriented matroid given by the so-called ``non-Pappus'' pseudoline configuration.

  

Figure 1.9: A zonotopal tiling corresponding to a non-realizable oriented matroid. This is indicated by the dotted ``pseudolines'' that form a configuration violating Pappus' Theorem (picture from ZIEGLER [75, p. 220]).

A zonotope $Z$ may be viewed as the projection $\pi (C_n)$ of the $n$-cube $C_n$. All those zonotopes that can appear in a zonotopal tiling of $Z$ are projections of faces of the $n'$-cube for some $n'$, possibly larger than $n$; thus all zonotopal tilings of $Z$ are $\pi '$-induced, where $\pi '(C_{n'}) = Z$. Hence, a proof of the Generalized Baues Conjecture in the special case of hypercube projections would imply a ``well-behaved'' structure of the set of all single-element liftings of a realizable oriented matroid.

Moreover, via oriented matroid duality, this ``cubical'' Generalized Baues Conjecture is in fact equivalent to the extension space conjecture (see [63, Introduction] for an overview of concepts in oriented matroid theory). Recently, a connection even between the set of all   triangulations of a point configuration and the extension space of its oriented matroid was drawn by SANTOS [65].

We only note here that there are several concepts of   triangulations of oriented matroids around. The first one was introduced by BILLERA & MUNSON [10], another one fitting in the theory of   combinatorial differential manifolds (see MACPHERSON [47]) was given by ANDERSON [2] (see SANTOS [65] for more information).

Our negative result in Chapter 2 shows that for a successful attack to the extension space conjecture via the cubical Generalized Baues Conjecture it is essential to take into account the particular structure of cube projections.