Introduction

Matroids (see [27]) and oriented matroids (see [11]) are axiomatic abstract

models for combinatorial geometry over general fields and over ordered fields, res-

pectively. Oriented matroids have some extra structure as compared to matroids,

one of whose features is the existence of a notion of convexity (see Chapter 9 of

[11]). This makes it natural to consider triangulations of oriented matroids as an

analogue of triangulations of usual polytopes or point configurations. This concept

is the object of this paper.

Triangulations of oriented matroids generalize the following situations, where

the oriented matroids involved are realized by geometric objects and where the

triangulations of the geometric objects considered are known to depend only on the

underlying oriented matroid:

• If M. is the oriented matroid of affine dependences between the vertices

of a polytope P, the triangulations of M coincide with the triangulations

of the polytope P, meaning by this the geometric simplicial complexes

which cover P and use only the vertices of P as vertices. There is a recent

survey by Lee [25] on this topic.

• If M. is the oriented matroid of affine dependences between the points

in a finite point set A in Rd, the triangulations of M coincide with the

triangulations of A, meaning by this the geometric simplicial complexes

which cover the convex hull of A and which use (perhaps not all) the

points of A as vertices. This is a generalization of the previous case

which has been often considered in recent literature (see [6, 13, 14, 15,

16, 28, 30, 36] and Chapter 7 of [19]).

• If M. is the oriented matroid of linear dependences between a finite set of

vectors V in

Rd,

the triangulations of M coincide with the triangulations

of V, meaning by this the simplicial fans covering the positive span of V

and whose rank-1 cones are generated by (perhaps not all) the vectors of

A- See [19, Definition 4.1] or [7]. This is a further generalization of the

previous case: if A is a point configuration in Rd, then triangulations of

A coincide with the simplicial fans of the vector configuration obtained

by embedding Rd as an affine hyperplane in the vector space Rrf+1.

Triangulations of oriented matroids were first defined by Billera and Munson

in [9], for the special case of polytopal oriented matroids. An account of them for

the more general case of acyclic oriented matroids appears in Section 9.6 of [11].

Deciding which is the best, or natural, definition of triangulation of a general

oriented matroid is not trivial. Apart of the problem of translating geometric

conditions into oriented matroid language, different possible characterizations of

triangulations in the realized case may translate to non-equivalent definitions in