CHAPTER 1

Preliminaries on Oriented Matroids

Throughout the paper we will assume familiarity with the basics of oriented

matroid theory. In this section we sum up the main specific concepts and properties

that we will need, related mainly to convexity and extensions. We will follow the

book by Bjorner et al. [11] for notation and reference, unless otherwise indicated.

Since we will be very seldom concerned with (non-oriented) matroids, we will

use the terms circuits, cocircuits, vectors and covectors always referring to signed

ones. We will indistinctly consider them signed subsets C = (C

+

,C~) of E or

functions C : E — { — 1,0, +1}, where E is the ground set of the oriented matroid.

Using the second point of view we can say that a circuit "is positive" or that it

"vanishes" at some elements of E, and will write C(p) = +1 with the same meaning

as p G C + , for p £ E. As usual, C_ denotes the support C + U C~ of C.

1.1. Convexity.

Let M be an oriented matroid of rank r on a set E. In order to stress the

geometrical meaning of oriented matroid concepts we will call simplices of M. the

independent subsets of E. A ^-simplex is a simplex with fc-elements. Thus, r-

simplices are the same thing as bases. If M. is a realizable oriented matroid and V C

Rr is a vector realization of M then the geometric counterpart of the /c-simplices of

J\A are simplicial cones of dimension k positively spanned by independent subsets

of M.. If Al is acyclic and realized by a point configuration A C

W~1

then the

^-simplices of M. correspond to simplices of A of dimension k — 1, with vertex set

contained in A.

Following [11, Chapter 9], we call facets of M the complements of supports of

non-negative cocircuits of M and faces the complements of supports of non-negative

covectors. Facets are the maximal proper faces (faces different from E itself). In

contrast with [11], we do not assume Ai to be acyclic. The faces of an oriented

matroid form a lattice called the Las Vergnas face lattice. The unique maximal face

is E and the unique minimal face is the family F0 of elements which lie in positive

circuits. It is the empty set if M. is acyclic. If M. is totally cyclic then FQ = E and

M has no proper faces.

For any A C E we denote by M(A) the restriction of M to A. We call faces

(resp. facets) of A the faces (resp. facets) of M(A). In particular, every subset of

a /c-simplex is a face of it, and it is a facet if and only if it has k — 1 elements. Of

course, all the faces of a simplex are simplices.

The convex hull of a subset A C E is the union of A and those elements p of

E \ A for which there is a signed circuit C of M with C

+

= {p} and C~ C A.

We denote this set by conv_^(A). The relative interior of A is the set obtained

7