On the Generation of Oriented Matroids

Abstract.

We provide a multiple purpose algorithm for generating oriented matroids. An application disproves a conjecture of Grünbaum that every closed triangulated orientable 2-manifold can be embedded geometrically in R ³ , i.e., with flat triangles and without self-intersections. We can show in particular that there exists an infinite class of orientable triangulated closed 2-manifolds for each genus g \geq 6 that cannot be embedded geometrically in Euclidean 3-space. Our algorithm is interesting in its own right as a tool for many investigations in which oriented matroids play a key role.