Matroid TheoryOxford University Press, 2006 - Počet stran: 532 The study of matroids is a branch of discrete mathematics with basic links to graphs, lattices, codes, transversals, and projective geometries. Matroids are of fundamental importance in combinatorial optimization and their applications extend into electrical engineering and statics. This incisive survey of matroid theory falls into two parts: the first part provides a comprehensive introduction to the basics of matroid theory while the second treats more advanced topics. The book contains over five hundred exercises and includes, for the first time in one place, short proofs for most of the subjects' major theorems. The final chapter lists sixty unsolved problems and details progress towards their solutions. |
Obsah
Basic definitions and examples | 7 |
12 Bases | 16 |
13 Rank | 22 |
14 Closure | 28 |
15 Geometric representations of matroids of small rank | 36 |
16 Transversal matroids | 46 |
17 The lattice of flats | 51 |
18 The greedy algorithm | 61 |
Higher connectivity | 271 |
82 Matroid versus graph connectivity | 277 |
83 3connected matroids and 2sums | 287 |
84 More properties of 3connected matroids | 292 |
Binary matroids | 303 |
92 Circuit and cocircuit spaces | 310 |
93 Other special properties | 315 |
Ternary matroids | 323 |
Duality | 68 |
22 Duals of representable matroids | 80 |
23 Duals of graphic matroids | 89 |
24 Duals of transversal matroids | 95 |
Minors | 104 |
32 Minors of certain classes of matroids | 111 |
33 Projection flats and the Scum Theorem | 117 |
Connectivity | 123 |
42 Properties of matroid connectivity | 128 |
43 More properties of connectivity | 133 |
Graphic matroids | 138 |
52 Duality in graphic matroids | 143 |
53 Whitneys 2lsomorphism Theorem | 147 |
54 Seriesparallel networks | 154 |
Representable matroids | 163 |
61 Projective geometries | 164 |
62 Affine geometries | 178 |
63 Different matroid representations | 185 |
64 Constructing representations for matroids | 190 |
65 Representability over finite fields | 202 |
66 Regular matroids | 209 |
67 Algebraic matroids | 215 |
68 Characteristic sets | 225 |
69 Modularity | 230 |
Constructions | 238 |
72 Singleelement extensions | 251 |
73 Quotients and related operations | 259 |
102 Some connectivity results | 331 |
103 The excludedminor characterization | 340 |
The Splitter Theorem | 346 |
112 Applications of the Splitter Theorem | 356 |
113 Variations on the Splitter Theorem | 370 |
Submodular functions and matroid union | 379 |
122 The theorems of Hall and Rado | 387 |
123 Matroid union and its applications | 402 |
124 Amalgams and the generalized parallel connection | 411 |
Regular matroids | 427 |
132 Seymours decomposition theorem | 435 |
133 The excludedminor characterization of graphic matroids | 440 |
134 Further properties of regular and graphic matroids | 454 |
Unsolved problems | 462 |
linear and algebraic | 463 |
142 Unimodal conjectures | 465 |
143 The critical problem | 468 |
144 From graphs to matroids | 469 |
145 Enumeration | 473 |
146 Matroid union | 474 |
147 Gammoids | 475 |
148 A miscellany | 476 |
| 479 | |
Appendix Some interesting matroids | 501 |
| 523 | |
| 525 | |
Běžně se vyskytující výrazy a sousloví
2-isomorphic 3-connected matroids algebraic algebraically dependent assume automorphism group B₁ basis binary matroids bipartite graph Brylawski C₁ Chapter characterization circuit cl(X class of matroids cocircuit cographic coloop column complete the proof conjecture contains contradiction Corollary corresponding cycle matroid deleting denote direct sum disjoint element entry equivalent Example excluded minors excluded-minor Exercise F-representable field F finite G₁ geometric representation GF(q graph G graphic matroids ground set Hence hyperplane identically self-dual incidence matrix independent sets Ingleton integer lattice Lemma Let G loop M₁ M1 and M2 M₂ Math matrix matroid theory minor isomorphic modular flat Moreover multiset N₁ non-empty non-zero obtained Oxley parallel minor planar graph plane polymatroid problem projective geometry properties Proposition Prove rank function rank-r regular matroids self-dual series paths Seymour shown in Figure simple matroid single-element strict gammoid subgraph submodular subsets suppose ternary matroids transversal matroids unique vertex vertices