This volume, the third in a sequence that began with The Theory of Matroids (1986) and Combinatorial Geometries (1987), concentrates on the applications of matroid theory to a variety of topics from geometry (rigidity and lattices), combinatorics (graphs, codes, and designs) and operations research (the greedy algorithm).
Author(s): Neil White
Series: Encyclopedia of mathematics and its applications 40
Edition: 1
Publisher: Cambridge University Press
Year: 2009
Language: English
Pages: 376
City: Cambridge [England]; New York
Tags: Математика;Дискретная математика;
Cover......Page 1
Half Title......Page 4
Series......Page 5
Title......Page 6
Copyright......Page 7
Contents......Page 8
List of Contributors ......Page 11
Preface ......Page 12
1.1 Bar Frameworks on the Line - The Graphic Matroid ......Page 14
1.2 Bar Frameworks in the Plane ......Page 16
1.3 Plane Stresses and Projected Polyhedra ......Page 24
1.4 Bar Frameworks in 3-space ......Page 29
1.5 A Matroid from Splines ......Page 37
1.6 Scene Analysis of Polyhedral Pictures ......Page 42
1.7 Special Positions ......Page 49
1.8 Conclusions ......Page 52
1.9 Historical Notes ......Page 53
Exercises ......Page 54
References ......Page 64
2.1 Introduction ......Page 67
2.2 Some Lattice Properties and Parameters of PMDs ......Page 69
2.3 Intersection Properties of the Hyperplane Family ......Page 71
2.4 PMDs of Rank 4 ......Page 75
2.5 Triffids ......Page 77
2.6 Some Close Relatives of PMDs and Further Directions ......Page 81
References ......Page 84
3.1 Pre-independence Spaces and Independence Spaces ......Page 86
3.2 B-matroids ......Page 93
Exercises ......Page 99
References ......Page 102
4.1 Introduction ......Page 104
4.2 Matroidal Families of Graphs: a Definition ......Page 105
4.3 Countably Many Matroidal Families ......Page 109
4.4 Uncountably Many Matroidal Families ......Page 111
4.5 Digraphs and Infinite Graphs ......Page 114
Exercises ......Page 115
References ......Page 117
5.1 Introduction ......Page 119
5.2 The Lattice of All Partitions ......Page 120
5.3 Lattice Embeddings ......Page 125
5.4 Postscript ......Page 131
Exercises ......Page 132
References ......Page 133
6.1 Introduction ......Page 136
6.2 The Tutte Polynomial ......Page 137
6.3 T-G Invariants in Graphs ......Page 149
6.4 The Critical Problem ......Page 175
6.5 Linear Codes ......Page 194
6.6 Other Tutte Invariants ......Page 201
Exercises ......Page 210
References ......Page 228
7.1 Introduction ......Page 239
7.2 Shellable Complexes ......Page 241
7.3 Matroid Complexes ......Page 245
7.4 Broken Circuit Complexes ......Page 251
7.5 Application to Matroid Inequalities ......Page 255
7.6 Order Complexes of Geometric Lattices ......Page 261
7.7 Homology of Shellable Complexes ......Page 265
7.8 Homology of Matroids ......Page 268
7.9 Homology of Geometric Lattices ......Page 272
7.10 The Orlik-Solomon Algebra ......Page 277
7.11 Notes and Comments ......Page 280
Exercises ......Page 283
References ......Page 294
8.1 Introduction ......Page 297
8.2 Definitions and Basic Facts ......Page 299
8.3 Examples ......Page 306
8.4 Structural Properties ......Page 315
8.5 Optimization on Greenoids ......Page 321
8.6 The Greedoid Polynomial ......Page 326
8.7 Antimatroids ......Page 332
8.8 Poset of Flats ......Page 340
8.9 Further Topics ......Page 348
8.10 Notes and Comments ......Page 356
Exercises ......Page 361
References ......Page 367
Index ......Page 371
