Book:Dominic Welsh/Matroid Theory
Jump to navigation
Jump to search
Dominic Welsh: Matroid Theory
Published $\text {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