Book:Dominic Welsh/Matroid Theory

From ProofWiki
Jump to navigation Jump to search

Dominic Welsh: Matroid Theory

Published $1976$, Dover Publications, Inc

ISBN 978-0-486-47439-7.


Subject Matter


Contents

Preface
Preliminaries
1 $\quad$ Basic notation
2 $\quad$ Set theory notation
3 $\quad$ Algebraic structures
4 $\quad$ Graph theory


Chapter 1. Fundamental Concepts and Examples
1 $\quad$ Introduction
2 $\quad$ Axiom systems for a matroid
3 $\quad$ Examples of matroids
4 $\quad$ Loops and parallel elements
5 $\quad$ Properties of independent sets and bases
6 $\quad$ Properties of the rank function
7 $\quad$ The closure operator
8 $\quad$ Closed sets = flats = subspaces
9 $\quad$ Circuits
10$\quad$ The cycle matroid of a graph
11$\quad$ A Euclidean representation of matroids of rank $\le 3$


Chapter 2. Duality
1 $\quad$ The dual matroid
2 $\quad$ The hyperplanes of a matroid
3 $\quad$ Paving matroids
4 $\quad$ The cocycle matroid of a graph


Chapter 3. Lattice Theory and Matroids
1 $\quad$ Brief review of lattice theory
2 $\quad$ The lattice of flats of a matroid
3 $\quad$ Geometric lattices and simple matroids
4 $\quad$ Partition lattices and Dilworth’s embedding theorem


Chapter 4. Submatroids
1 $\quad$ Truncation
2 $\quad$ Restriction
3 $\quad$ Contraction
4 $\quad$ Minors and their representation in the lattice


Chapter 5. Matroid Connection
1 $\quad$ Two theorems about circuits and cocircuits
2 $\quad$ Connectivity
3 $\quad$ Direct product of lattices, direct sum of matroids
4 $\quad$ Descriptions of matroids
5 $\quad$ The circuit graph of a matroid; a lattice Characterization of connection
6 $\quad$ Tutte’s theory of $n$-connection: wheels and whirls


Chapter 6. Matroids, Graphs and Planarity
1 $\quad$ Unique representations of graphic matroids-the importance of $3$-connection
2 $\quad$ Homeomorphism of graphs and matroid minors
3 $\quad$ Planar graphs and their geometric dual
4 $\quad$ Planar graphs and their abstract dual
5 $\quad$ Conditions for a graph to be planar


Chapter 7. Transversal Theory
1 $\quad$ Transversals and partial transversals; the Rado-Hall theorems
2 $\quad$ A generalisation of the Rado-Hall theorem
3 $\quad$ Transversals matroids
4 $\quad$ Transversals with prescribed properties-applications of Rado’s theorem
5 $\quad$ Generalised transversals
6 $\quad$ A “converse” to Rado’s theorem


Chapter 8. Covering and Packing
1 $\quad$ Submodular functions
2 $\quad$ Functions of matroids; inducing matroids by bipartite graphs
3 $\quad$ The union of matroids
4 $\quad$ Covering and packing theorems
5 $\quad$ Edmond’s intersection theorem


Chapter 9. The Vector Representation of Matroids
1 $\quad$ The representability problem
2 $\quad$ Some non-representable matroids
3 $\quad$ The representability of minors, duals, and truncations
4 $\quad$ Chain groups
5 $\quad$ Representability of graphic matroids
6 $\quad$ The representability of induced matroids, unions of matroids and transversal matroids
7 $\quad$ The characteristic set of a matroid
8 $\quad$ Conditions for representability


Chapter 10. Binary Matroids
1 $\quad$ Equivalent conditions for representability over $GF(2)$
2 $\quad$ An excluded minor criterion for a matroid to be binary
3 $\quad$ The circuit space and cocircuit space; orientable matroids
4 $\quad$ Regular matroids
5 $\quad$ Conditions for a matroid to be graphic or cographic
6 $\quad$ Simplicial matroids


Chapter 11. Matroids from Fields and Groups
1 $\quad$ Algebraic matroids
2 $\quad$ The relation between algebraic and linear representability
3 $\quad$ Operations on algebraic matroids
4 $\quad$ Partition matroids determined by finite groups


Chapter 12. Block Designs and Matroids
1 $\quad$ Projective and affine spaces —-
2 $\quad$ Block designs and Steiner systems
3 $\quad$ Matroids and block designs
4 $\quad$ Theorems of Dembowski, Wagner and Kantor
5 $\quad$ Perfect matroid designs
6 $\quad$ The Steiner system $S(5, 8, 24)$ and its subsystems


Chapter 13. Menger’s Theorem and Linkings in Graphs
1 $\quad$ The basic linkage lemma
2 $\quad$ Gammoids
3 $\quad$ Matroids induced by linkings
4 $\quad$ A new class of matroids from graphs


Chapter 14. Transversal Matroids and Related Topics
1 $\quad$ Base orderable matroids
2 $\quad$ Series parallel networks and extensions of matroids
3 $\quad$ Graphic transversal matroids
4 $\quad$ An equivalent class of binary structures
5 $\quad$ Properties of transversal matroids
6 $\quad$ Matchings in graphs


Chapter 15. Polynomials, Colouring Problems, Codes and Packages
1 $\quad$ The chromatic polynomial of a graph
2 $\quad$ The Möbius function of a partially ordered set
3 $\quad$ The chromatic or characteristic polynomial of a matroid
4 $\quad$ The Tuttle polynomial and Whitney rank generating function
5 $\quad$ The critical problem
6 $\quad$ Codes, packings and the critical problem
7 $\quad$ Weight enumeration of codes: the MacWilliams’ identity


Chapter 16. Extremely Problems
1 $\quad$ Introduction
2 $\quad$ The Whitney numbers and the unimodal conjecture
3 $\quad$ The Dowling-Wilson theorems
4 $\quad$ Bases and independent sets
5 $\quad$ Sperner’s lemma and Ramsey’s theorem
6 $\quad$ Enumeration


Chapter 17. Maps between Matroids and Geometric Lattices
1 $\quad$ Strong maps between geometric lattices
2 $\quad$ Factorisation theorems for strong maps
3 $\quad$ Single element extensions
4 $\quad$ Strong maps induced by the identity functions
5 $\quad$ The scum theorem
6 $\quad$ Erections of matroids
7 $\quad$ The automorphism group of a matroid


Chapter 18. Convex Polytopes associated with Matroids
1 $\quad$ Convex polytopes and linear programming
2 $\quad$ Polymatroids
3 $\quad$ Polymatroids and submodular set functions
4 $\quad$ Vertices of polymatroids
5 $\quad$ A new class of polytopes with integer vertices
6 $\quad$ Further results on polymatroids
7 $\quad$ Supermatroids


Chapter 19. Combinatorial Optimisation
1 $\quad$ The greedy algorithm
2 $\quad$ A greedy algorithm for a class of linear programmes
3 $\quad$ Partitioning and intersection algorithms
4 $\quad$ Lehman’s solution of the Shannon switching game
5 $\quad$ An extension of network flow theory
6 $\quad$ Some intractable problems


Chapter 20. Infinite Structures
1 $\quad$ Pre-independence spaces
2 $\quad$ Independence spaces
3 $\quad$ Infinite transversal theory
4 $\quad$ Duality in independence spaces
5 $\quad$ The operator approach to duality


Bibliography
Index of symbols
Index