# Book:Dominic Welsh/Matroid Theory

Jump to navigation
Jump to search
## Dominic Welsh:

## 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