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

   
Oriented Matroids

Further information can be found in the book Oriented Matroids by BJÖRNER, LAS VERGNAS, STURMFELS, WHITE & ZIEGLER [15]. A shorter introduction to important modern concepts in oriented matroid theory is by RICHTER-GEBERT [63].

Definition 4.5.1   Let $E$ be a finite set. For   sign vectors $X \in \{ -,0,+ \}^E$, we define           $$\begin{align*}0^E &:= (0, \dots , 0),\\ \supp (X) &:= \setof{e \in E}{X_e \neq... ...Y_e & \text{otherwise}. \end{array} \right. \tag*{(composition)} \end{align*}$$

A set $\mathcal{V}^*$ of sign vectors in $\{ -,0,+ \}^E$ is a set of   covectors in $E$ if it satisfies the following conditions.

(CV0)

$0^E \in \mathcal{V}^*$,

(CV1)

$X \in \mathcal{V}^*$ implies $-X \in \mathcal{V}^*$,

(CV2)

$X, Y \in \mathcal{V}^*$ implies $X \circ Y \in \mathcal{V}^*$,

(CV3)

if $X, Y \in \mathcal{V}^*$ and $e \in S(X,Y)$, then there exists $Z \in \mathcal{V}^*$ such that $Z_e = 0$ and $Z_f = (X \circ Y)_f = (Y \circ X)_f$ for all $f \notin S(X,Y)$.

An   oriented matroid is a pair $\mathcal{M} = (E, \mathcal{V}^*)$, where E is a finite set, and $\mathcal{V}^*$ is a set of covectors in $E$. The   big face lattice $\mathcal{F}(\mathcal{M})$ of an oriented matroid $\mathcal{M}$ is the poset $(\mathcal{V}^*, \le)$, where ``$\le$'' denotes the inclusion of supports. The   rank $r(\mathcal{M})$ of $\mathcal{M}$ is the rank of $\mathcal{F}(\mathcal{M})$. A non-zero covector with inclusion-minimal support is called a   cocircuit.

For $E' \subset E$, the   restriction of $X \in \{ -,0,+ \}^E$ to $E'$ is the sign vector $X_{E'} \in \{ -,0,+ \}^{E'}$ on $E'$ that coincides with $X$ on $E'$. We define    

$$\begin{align*}\mathcal{V}^* \sm E' &:= \setof{X_{E \sm E'}}{X \in \mathcal{V}^*... ... E'}}{X \in \mathcal{V}^*, X_{E'} = 0^{E'}}. \tag*{(contraction)} \end{align*}$$ This gives rise to the corresponding oriented matroids $$\begin{align*}\mathcal{M} \sm E' &:= (E \sm E', \mathcal{V}^* \sm E'),\\ \mathcal{M} / E' &:= (E \sm E', \mathcal{V}^* / E'). \end{align*}$$

An element $e \in E$ is a   loop of $\mathcal{M}$ if $X_e = 0$ for all $X \in \mathcal{V}^*$. It is a   coloop if $r(\mathcal{M} \sm e) < r(\mathcal{M})$. A     (one-element) lifting of $\mathcal{M}$ is an oriented matroid $\widehat{\mathcal{M}}$ on $E \uplus g$ such that $\mathcal{M} = \widehat{\mathcal{M}} / g$ and $g$ is not a loop of $\widehat{\mathcal{M}}$. A     (single-element) extension of $\mathcal{M}$ is an oriented matroid on $E \uplus g$ such that $\mathcal{M} = \widehat{\mathcal{M}} \sm g$ and $g$ is neither a loop nor a coloop of $\widehat{\mathcal{M}}$.

Let $\mathcal{M}$ and $\mathcal{N}$ be oriented matroids on $E$. $\mathcal{N}$ is a   strong image of $\mathcal{M}$ if every covector of $\mathcal{N}$ is also a covector of $\mathcal{M}$. $\mathcal{N}$ is a   weak image of $\mathcal{M}$ if $\mathcal{M}$ and $\mathcal{N}$ are of the same rank, and for every covector $X$ of $\mathcal{N}$ there is a covector $Y$ of $\mathcal{M}$ with $X \le Y$. We write $\mathcal{N} \le \mathcal{M}$ if $\mathcal{N}$ is a weak image of $\mathcal{M}$. This yields a partial order ``$\le$'' on the set of all oriented matroids, the   weak map relation.

Definition 4.5.2   Let $V = (v_1, \dots , v_n)$ be a vector configuration in $\mathbb{R} ^d$. The   oriented matroid $\mathcal{M}(V)$ of $V$ is defined by its ground set $[n] := \{ 1, \dots , n \}$ and its set of covectors

$$\mathcal{V}^*(V) := \setof{ \bigl(\sign (\psi (v_1)), \dots... ...igr)}{ \psi \in (\mathbb{R} ^d)^*} \subseteq \{ -,0,+ \}^n.$$

The oriented matroid $\mathcal{F}^d$ of $d$ linearly independent vectors in $\mathcal{R}^d$ is called the   free oriented matroid on $d$ elements. An oriented matroid $\mathcal{M}$ is   realizable if $\mathcal{M} = \mathcal{M}(V)$ for some vector configuration $V$.

The reader may get a picture of covectors by thinking of some linear oriented hyperplane (corresponding to the $\psi$ in the definition above) in $\mathbb{R} ^d$ partitioning the vectors in $V$ into vectors on the hyperplane, vectors on its positive, and vectors on its negative side, thus defining a sign vector. Alternatively, one can consider the   arrangement of hyperplanes given by the vectors in $V$, viewed as normal vectors of hyperplanes $H_{v_i}$ in $\mathbb{R} ^d$. This arrangement divides $\mathbb{R} ^d$into cells. For every open cell $c$, we get a sign-vector $\sigma (c)$corresponding to a covector by setting

$$\sigma(c)_i = \left\{ \begin{array}{rl} + & \text{if $c$\s... ...0 & \text{if $c$\space is on $H_{v_i}$ }. \end{array} \right.$$

Vertices in this cell decomposition correspond to cocircuits. The latter interpretation may be generalized to   pseudosphere arrangements on the $d$-sphere with certain intersection properties. This generalization encompasses all oriented matroids via the Topological Representation Theorem by FOLKMAN & LAWRENCE [27].