Oriented matroids

Cover......Page 1
Title......Page 4
Copyright......Page 5
Contents......Page 6
Preface......Page 10
Preface to the Second Edition......Page 11
Notation......Page 12
1.1 Oriented matroids from directed graphs......Page 14
1.2 Point configurations and hyperplane arrangements......Page 18
1.3 Pseudoline arrangements......Page 27
1.4 Topological Representation Theorem......Page 30
1.5 Realizability......Page 33
1.6 Combinatorial convexity......Page 37
1.7 Linear programming......Page 39
1.8 Computational geometry......Page 42
1.9 Chirality in molecular chemistry......Page 46
1.10 Allowable sequences......Page 48
1.11 Slope problems......Page 52
Exercises......Page 55
2.1 Real hyperplane arrangements......Page 59
2.2 Zonotopes......Page 63
2.3 Reflection arrangements......Page 78
2.4 Stratification of the Grassmann variety......Page 90
2.5 Complexified arrangements......Page 105
Exercises......Page 108
3.1 Introductory remarks......Page 113
3.2 Circuits......Page 116
3.3 Minors......Page 123
3.4 Duality......Page 128
3.5 Basis orientations and chirotopes......Page 136
3.6 Modular elimination and local realizability......Page 148
3.7 Vectors and covectors......Page 154
3.8 Maximal vectors and topes......Page 159
3.9 Historical sketch......Page 163
Exercises......Page 164
4. From Face Lattices to Topology......Page 170
4.1 The big face lattice......Page 171
4.2 Topes I......Page 182
4.3 Shellability and sphericity......Page 188
4.4 Topes II......Page 194
4.5 The affine face lattice......Page 199
4.6 Enumeration of cells......Page 206
4.7 Appendix: Regular cell complexes, posets and shellability......Page 213
Exercises......Page 229
5.1 Arrangements of pseudospheres......Page 238
5.2 The topological representation theorem......Page 245
5.3 Pseudoconfigurations of points......Page 249
Exercises......Page 257
6.1 Arrangements of pseudospheres in low dimensions......Page 260
6.2 Arrangements of pseudolines......Page 263
6.3 How far can things be stretched?......Page 272
6.4 Allowable sequences, wiring diagrams and homotopy......Page 277
6.5 Three enumerative questions......Page 282
6.6 Orientable matroids of rank 3......Page 285
Exercises......Page 290
7.1 Single element extensions......Page 294
7.2 Lexicographic extensions and the extension lattice......Page 304
7.3 Local perturbations and mutations......Page 309
7.4 Many oriented matroids......Page 318
7.5 Intersection properties and adjoints......Page 321
7.6 Direct sum and union......Page 325
7.7 Strong maps and weak maps......Page 331
7.8 Inseparability graphs......Page 337
7.9 Orientability......Page 342
Exercises......Page 345
8.1 The realization space of an oriented matroid......Page 351
8.2 Constructions and realizability results......Page 355
8.3 The impossibility of a finite excluded minor characterization......Page 361
8.4 Algorithms and complexity results......Page 366
8.5 Final polynomials and the real Nullstellensatz......Page 371
8.6 The isotopy problem and Mnev\'s universality theorem......Page 376
8.7 Oriented matroids and robust computational geometry......Page 382
Exercises......Page 386
9.1 Introduction to matroid polytopes......Page 389
9.2 Convexity results and constructions......Page 394
9.3 The Lawrence construction and its applications......Page 399
9.4 Cyclic and neighborly matroid polytopes......Page 408
9.5 The Steinitz problem and its relatives......Page 416
9.6 Polyhedral subdivisions and triangulations......Page 421
Exercises......Page 425
10. Linear Programming......Page 430
10.1 Affine oriented matroids and linear programs......Page 432
10.2 Pivot steps and tableaux......Page 446
10.3 Pivot rules......Page 464
10.4 Examples......Page 474
10.5 Euclidean matroids......Page 485
Exercises......Page 490
A.1 Realization spaces......Page 493
A.2 Spaces of oriented matroids......Page 495
A.3 Triangulations......Page 497
A.4 Zonotopal tilings......Page 498
A.5 Realization algorithms......Page 499
A.6 Random walks on arrangements......Page 500
A.7 Polyhedral 2-manifolds......Page 501
Bibliography......Page 502
Index......Page 555