You are here

Matroid Theory

D. J. A. Welsh
Publisher: 
Dover Publications
Publication Date: 
2010
Number of Pages: 
448
Format: 
Paperback
Price: 
20.95
ISBN: 
9780486474397
Category: 
Monograph
[Reviewed by
Darren Glass
, on
01/8/2016
]

There are many different ways to define a matroid, but perhaps the most straightforward is to think of a finite set \(S\) with a collection \(\mathcal{I}\) of subsets of \(S\) that satisfies the following three properties:

  • The empty set is in \(\mathcal{I}\).
  • If \(I \in \mathcal{I}\) and \(J \subseteq I\) then \(J \in \mathcal{I}\).
  • If \(I\) and \(J\) are both in \(\mathcal{I}\) and \(|I| < |J|\), then there exists \(y \in J \setminus I\) so that \(\hat{I}=I \cup \{ y \} \in \mathcal{I}\). 

While these axioms may seem odd at first glance, they were originally developed by Whitney in the 1930s as a way of generalizing the notion of linear independence in vector spaces. For this reason, the set \(\mathcal{I}\) is typically referred to as the collection of independent subsets. Over the last 80 years there have been many different applications, examples, and extensions of these ideas defined. For a short and modern take on matroids and their applications in tropical geometry, I recommend this blog post by Matt Baker. For a somewhat longer modern take, I recommend James Oxley’s article "What is a Matroid?" For the reader who is interested in a deeper dive into the material, there have been several good books written on the subject. One of these is the book by Dominic Welsh that is under review.

Welsh came to matroids by way of graph theory, which is a natural source of examples in the field. In particular, for any finite graph one can define its cycle matroid by letting the set \(S\) be the set of edges of the graph, and \(\mathcal{I}\) consist of all subsets of \(S\) that do not contain a cycle. While not all matroids come from graphs in this way, it turns out that one can prove many theorems about matroids in general by translating theorems and proofs about graphs to this setting, and Welsh wrote a number of papers doing just this.

In 1976, Welsh wrote this book, entitled simply Matroid Theory as an attempt to summarize both his own work and the role that matroids were playing in many other parts of combinatorics during the 1960s and 1970s. It was one of the first comprehensive treatments of the subject, and while several others have been written over the years, Dover has recently reissued the book to make it available to a modern audience. When it was first published, Gian-Carlo Rota wrote of the book:

In this beautifully written and exceptionally thorough book, the case is made for one of the strangest and most mysterious notions ever to come out of the primeval forest of combinatorics, a generalization of linear algebra that is knocking at the algebraist’s door, whose depth is matched only by its stubborn resistance to being reduced to any of the known versions of classical algebraic thinking.

Looking at it forty years later, Welsh’s book shows its age in many ways — as mentioned above, matroids have continued to find many new applications that Welsh could not have dreamed of at the time (although many of them are due to his own subsequent work!), and aspects of both the exposition and typesetting are clearly a product of their time. The book can be quite terse, and I did not find it to be as friendly an introduction to the area as one might hope for, but at the same time it begins in a very elementary way and builds to some significant results. At the price of a Dover book, it will serve as a good reference in many personal libraries.


Darren Glass is an Associate Professor of Mathematics at Gettysburg College whose mathematical interests include graph theory, number theory, and algebraic geoemtry. He can be reached at dglass@gettysburg.edu.

The table of contents is not available.