Oriented matroids. 2nd ed.

*(English)*Zbl 0944.52006
Encyclopedia of Mathematics and Its Applications. 46. Cambridge: Cambridge University Press. xii, 548 p. (1999).

This book is a comprehensive exposition of oriented matroids consisting of ten chapters. It is intended for graduate students as an introduction (where some knowledge in discrete mathematics is of advantage) and for researchers who need a thorough reference work.

The book starts with two orientation sessions which illustrate different aspects of oriented matroids. Since oriented matroids can be thought of as combinatorial abstraction of directed graphs, of real hyperplane arrangements, of point configurations, and of convex polytopes, these mathematical theories are used to motivate oriented matroids. In these two chapters a number of examples is presented and simultaneously the main concepts and terminology of oriented matroids is introduced.

In the third chapter a formal introduction is given by presenting four basic axiom systems for oriented matroids: circuit axioms, orthogonality axioms, chirotopes, and vector axioms. These axiom systems arise from directed graphs, orthogonal pairs of real vector subspaces, point configurations and convex polytopes, and real hyperplane arrangements, respectively. Other topics discussed in this chapter include minors, duality, and local realizability.

Chapter 4 is entitled “From Face Lattices to Topology”. Face lattices are studied in this chapter in a general axiomatized version. The lattices are formed by the covectors of an oriented matroid under a natural partial ordering. The connection to topology is established by showing that the covector lattice of an oriented matroid uniquely determines a regular cell decomposition of a sphere.

In Chapter \(5\) topological models for oriented matroids are presented. The core of this chapter is the Topological Representation Theorem. It says that general oriented matroids similarly correspond to arrangements of generalized hyperplanes, each obtained from a flat hyperplane by tame topological deformation. The rank 3 case of the Topological Representation Theorem can easily be visualized. In the projective version, this identifies rank 3 oriented matroids with arrangements of pseudolines. These arrangements are the topic of Chapter \(6\).

In Chapter \(7\) it is discussed how oriented matroids can be extended, deformed, locally perturbed, flipped, glued together, and how the old and the newly obtained oriented matroids are related. The realizability of oriented matroids is the topic of Chapter \(8\). To this for the space \({\mathcal R}(M)\) of all vector realizations of a fixed oriented matroid M is introduced. The realizability problem for M now becomes the question whether the semialgebraic variety \({\mathcal R}(M)\) is empty or not.

Chapter \(9\) is devoted to the combinatorial theory of convex polytopes. Several new results on polytopes as well as new simplified proofs for known results could be found with the help of oriented matroid theory. Chapter \(10\) gives an introduction to linear programming on oriented matroids. A geometric access to the fundamental ideas of oriented matroid programming, as developed by Bland is given.

A list of open problems and exercises is included after each of the ten chapters. In the second edition an appendix has been added about some current frontiers of research. Here, the progress made since the first edition was published is summarized. Also the already excellent bibliography of the first edition has been greatly expanded.

The book starts with two orientation sessions which illustrate different aspects of oriented matroids. Since oriented matroids can be thought of as combinatorial abstraction of directed graphs, of real hyperplane arrangements, of point configurations, and of convex polytopes, these mathematical theories are used to motivate oriented matroids. In these two chapters a number of examples is presented and simultaneously the main concepts and terminology of oriented matroids is introduced.

In the third chapter a formal introduction is given by presenting four basic axiom systems for oriented matroids: circuit axioms, orthogonality axioms, chirotopes, and vector axioms. These axiom systems arise from directed graphs, orthogonal pairs of real vector subspaces, point configurations and convex polytopes, and real hyperplane arrangements, respectively. Other topics discussed in this chapter include minors, duality, and local realizability.

Chapter 4 is entitled “From Face Lattices to Topology”. Face lattices are studied in this chapter in a general axiomatized version. The lattices are formed by the covectors of an oriented matroid under a natural partial ordering. The connection to topology is established by showing that the covector lattice of an oriented matroid uniquely determines a regular cell decomposition of a sphere.

In Chapter \(5\) topological models for oriented matroids are presented. The core of this chapter is the Topological Representation Theorem. It says that general oriented matroids similarly correspond to arrangements of generalized hyperplanes, each obtained from a flat hyperplane by tame topological deformation. The rank 3 case of the Topological Representation Theorem can easily be visualized. In the projective version, this identifies rank 3 oriented matroids with arrangements of pseudolines. These arrangements are the topic of Chapter \(6\).

In Chapter \(7\) it is discussed how oriented matroids can be extended, deformed, locally perturbed, flipped, glued together, and how the old and the newly obtained oriented matroids are related. The realizability of oriented matroids is the topic of Chapter \(8\). To this for the space \({\mathcal R}(M)\) of all vector realizations of a fixed oriented matroid M is introduced. The realizability problem for M now becomes the question whether the semialgebraic variety \({\mathcal R}(M)\) is empty or not.

Chapter \(9\) is devoted to the combinatorial theory of convex polytopes. Several new results on polytopes as well as new simplified proofs for known results could be found with the help of oriented matroid theory. Chapter \(10\) gives an introduction to linear programming on oriented matroids. A geometric access to the fundamental ideas of oriented matroid programming, as developed by Bland is given.

A list of open problems and exercises is included after each of the ten chapters. In the second edition an appendix has been added about some current frontiers of research. Here, the progress made since the first edition was published is summarized. Also the already excellent bibliography of the first edition has been greatly expanded.

Reviewer: Stefan Nickel (Kaiserslautern)

##### MSC:

52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |

52-02 | Research exposition (monographs, survey articles) pertaining to convex and discrete geometry |

05B35 | Combinatorial aspects of matroids and geometric lattices |

05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |

90C05 | Linear programming |

52C40 | Oriented matroids in discrete geometry |

68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |