Book:Dominic Welsh/Matroid Theory

Dominic Welsh: Matroid Theory

Published $\text {1976}$, Dover Publications, Inc

ISBN 978-0-486-47439-7

Subject Matter

• Matroid Theory

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