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
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
Previous Page Next Page