Oriented Matroids

by Anders Björner , Michel Las Vergnas , Bernd Sturmfels , Neil White , Gunter M. Ziegler

• ISBN13: 9780521777506
• ISBN10: 052177750X
• Edition: 2nd
• Format: Paperback
• Copyright: 2000-01-28
• Publisher: Cambridge University Press

Summary

Oriented matroids are a very natural mathematical concept which presents itself in many different guises and which has connections and applications to many different areas. These include discrete and computational geometry, combinatorics, convexity, topology, algebraic geometry, operations research, computer science and theoretical chemistry. This is the second edition of the first comprehensive, accessible account of the subject. It is intended for a diverse audience: graduate students who wish to learn the subject from scratch; researchers in the various fields of application who want to concentrate on certain aspects of the theory; specialists who need a thorough reference work; and others at academic points in between. A list of exercises and open problems ends each chapter. For the second edition, the authors have expanded the bibliography greatly to ensure that it remains comprehensive and up-to-date, and they have also added an appendix surveying research since the work was first published.

Table of Contents

Preface	ix
Preface to the Second Edition	x
Notation	xi
A First Orientation Session	1	(45)
Oriented matroids from directed graphs	1	(4)
Point configurations and hyperplane arrangements	5	(9)
Pseudoline arrangements	14	(3)
Topological Representation Theorem	17	(3)
Realizability	20	(4)
Combinatorial convexity	24	(2)
Linear programming	26	(3)
Computational geometry	29	(4)
Chirality in molecular chemistry	33	(2)
Allowable sequences	35	(4)
Slope problems	39	(7)
Exercises	42	(4)
A Second Orientation Session	46	(54)
Real hyperplane arrangements	46	(4)
Zonotopes	50	(15)
Reflection arrangements	65	(12)
Stratification of the Grassmann variety	77	(15)
Complexified arrangements	92	(8)
Exercises	95	(5)
Axiomatics	100	(57)
Introductory remarks	100	(3)
Circuits	103	(7)
Minors	110	(5)
Duality	115	(8)
Basis orientations and chirotopes	123	(12)
Modular elimination and local realizability	135	(6)
Vectors and covectors	141	(5)
Maximal vectors and topes	146	(4)
Historical sketch	150	(7)
Exercises	151	(6)
From Face Lattices to Topology	157	(68)
The big face lattice	158	(1)
Topes I	159	(16)
Shellability and sphericity	175	(6)
Topes II	181	(5)
The affine face lattice	186	(7)
Enumeration of cells	193	(7)
Appendix: Regular cell complexes, posets and shellability	200	(25)
Exercises	216	(9)
Topological Models for Oriented Matroids	225	(22)
Arrangements of pseudospheres	225	(7)
The topological representation theorem	232	(4)
Pseudoconfigurations of points	236	(11)
Exercises	244	(3)
Arrangements of Pseudolines	247	(34)
Arrangements of pseudospheres in low dimensions	247	(3)
Arrangements of pseudolines	250	(9)
How far can things be stretched?	259	(5)
Allowable sequences, wiring diagrams and homotopy	264	(5)
Three enumerative questions	269	(3)
Orientable matroids of rank 3	272	(9)
Exercises	277	(4)
Constructions	281	(57)
Single element extensions	281	(10)
Lexicographic extensions and the extension lattice	291	(5)
Local perturbations and mutations	296	(9)
Many oriented matroids	305	(3)
Intersection properties and adjoints	308	(4)
Direct sum and union	312	(6)
Strong maps and weak maps	318	(6)
Inseparability graphs	324	(5)
Orientability	329	(9)
Exercises	332	(6)
Realizability	338	(38)
The realization space of an oriented matroid	338	(4)
Constructions and realizability results	342	(6)
The impossibility of a finite excluded minor characterization	348	(5)
Algorithms and complexity results	353	(5)
Final polynomials and the real Nullstellensatz	358	(5)
The isotopy problem and Mnev's universality theorem	363	(6)
Oriented matroids and robust computational geometry	369	(7)
Exercises	373	(3)
Convex Polytopes	376	(41)
Introduction to matroid polytopes	376	(5)
Convexity results and constructions	381	(5)
The Lawrence construction and its applications	386	(9)
Cyclic and neighborly matroid polytopes	395	(8)
The steinitz problem and its relatives	403	(5)
Polyhedral subdivisions and triangulations	408	(9)
Exercises	412	(5)
Linear Programming	417	(63)
Affine oriented matroids and linear programs	419	(14)
Pivot steps and tableaux	433	(18)
Pivot rules	451	(10)
Examples	461	(11)
Euclidean matroids	472	(8)
Exercises	477	(3)
Appendix: Some Current Frontiers of Research	480	(9)
A.1 Realization spaces	480	(2)
A.2 Spaces of oriented matroids	482	(2)
A.3 Triangulations	484	(1)
A.4 Zonotopal tilings	485	(1)
A.5 Realization algorithms	486	(1)
A.6 Random walks on arrangements	487	(1)
A.7 Polyhedral 2-manifolds	488	(1)
Bibliography	489	(53)
Index	542