Preliminaries ................................................... 1
1 Basic definitions and examples ............................... 7
1.1 Independent sets and circuits ........................... 7
1.2 Bases .................................................. 15
1.3 Rank ................................................... 20
1.4 Closure ................................................ 25
1.5 Geometric representations of matroids of small rank .... 32
1.6 Transversal matroids ................................... 43
1.7 The lattice of flats ................................... 48
1.8 The greedy algorithm ................................... 58
2 Duality ..................................................... 64
2.1 The definition and basic properties .................... 64
2.2 Duals of representable matroids ........................ 77
2.3 Duals of graphic matroids .............................. 87
2.4 Duals of transversal matroids .......................... 93
3 Minors ..................................................... 100
3.1 Contraction ........................................... 100
3.2 Minors of certain classes of matroids ................. 106
3.3 The Scum Theorem, projection, and flats ............... 113
4 Connectivity ............................................... 118
4.1 Connectivity for graphs and matroids .................. 118
4.2 Properties of matroid connectivity .................... 122
4.3 More properties of connectivity ....................... 126
5 Graphic matroids ........................................... 135
5.1 Representability ...................................... 135
5.2 Duality in graphic matroids ........................... 140
5.3 Whitney's 2-Isomorphism Theorem ....................... 145
5.4 Series-parallel networks .............................. 151
6 Representable matroids ..................................... 158
6.1 Projective geometries ................................. 159
6.2 Affine geometries ..................................... 170
6.3 Different matroid representations ..................... 176
6.4 Constructing representations for matroids ............. 181
6.5 Representability over finite fields ................... 192
6.6 Regular matroids ...................................... 204
6.7 Algebraic matroids .................................... 211
6.8 Characteristic sets and decidability .................. 220
6.9 Modularity ............................................ 228
6.10 Dowling geometries .................................... 235
7 Constructions .............................................. 251
7.1 Series and parallel connection and 2-sums ............. 251
7.2 Single-element extensions ............................. 264
7.3 Quotients and related operations ...................... 272
7.4 A non-commutative operation ........................... 282
8 Higher connectivity ........................................ 291
8.1 Tutte's definition .................................... 291
8.2 Properties of the connectivity function ............... 296
8.3 3-connected matroids and 2-sums ....................... 304
8.4 Wheels and whirls ..................................... 316
8.5 Tutte's Linking Theorem and its applications .......... 319
8.6 Matroid versus graph connectivity ..................... 324
8.7 Some extremal connectivity results .................... 332
8.8 Tutte's Wheels-and-Whirls Theorem ..................... 337
9 Binary matroids ............................................ 344
9.1 Characterizations ..................................... 344
9.2 Circuit and cocircuit spaces .......................... 349
9.3 The operation of 3-sum ................................ 353
9.4 Other special properties .............................. 360
10 Excluded-minor theorems .................................... 372
10.1 The characterization of regular matroids .............. 372
10.2 The characterization of ternary matroids .............. 380
10.3 The characterization of graphic matroids .............. 385
10.4 Further properties of regular and graphic matroids .... 398
11 Submodular functions and matroid union ..................... 404
11.1 Deriving matroids from submodular functions ........... 404
11.2 The theorems of Hall and Rado ......................... 411
11.3 Matroid union and its applications .................... 427
11.4 Amalgams and the generalized parallel connection ...... 436
11.5 Generalizations of delta-wye exchange ................. 448
12 The Splitter Theorem ....................................... 457
12.1 The theorem and its proof ............................. 457
12.2 Applications of the Splitter Theorem .................. 465
12.3 Variations on the Splitter Theorem .................... 477
13 Seymour's Decomposition Theorem ............................ 489
13.1 Overview .............................................. 489
13.2 Graphic, cographic, or a special minor ................ 494
13.3 Blocking sequences .................................... 507
13.4 R12-minors ............................................. 517
14 Research in representability and structure ................. 525
14.1 The Well-Quasi-Ordering Conjecture for Matroids ....... 525
14.2 Branch-width .......................................... 529
14.3 Rota's Conjecture and the Well-Quasi-Ordering
Conjecture ............................................ 536
14.4 Algorithmic consequences .............................. 540
14.5 Intertwining .......................................... 543
14.6 Inequivalent representations .......................... 550
14.7 Ternary, matroids ..................................... 555
14.8 Stabilizers ........................................... 561
14.9 Unavoidable minors .................................... 569
14.10 Growth rates ......................................... 570
15 Unsolved problems .......................................... 583
15.1 Representability: linear and algebraic ................ 584
15.2 Unimodal conjectures .................................. 585
15.3 Critical problems ..................................... 588
15.4 From graphs to matroids ............................... 591
15.5 Enumeration ........................................... 593
15.6 Gammoids and transversal matroids ..................... 598
15.7 Excluding a uniform matroid ........................... 599
15.8 Negative correlation .................................. 600
15.9 A miscellany .......................................... 604
References .................................................... 608
Appendix: Some interesting matroids ........................... 639
List of tables ................................................ 665
Notation ...................................................... 666
Index ......................................................... 668
|
