Feature Column from the AMS

Matroids: The Value of Abstraction

4. The development of a theory of matroids

The person generally credited with beginning the theory of matroids was Hassler Whitney (1907-1989). Whitney was a towering figure in American mathematics, having made major contributions to the theory of graphs and to topology. A whole host of mathematical objects are named after him, including several different Whitney numbers.

Quick to develop the idea and related areas were Saunders Mac Lane (1909-) and Garrett Birkhoff (1911-1996), whose names are also linked for being the authors of an influential book on modern algebra for undergraduates.

Photo of Garret Birkhoff and Saunders Mac Lane

Mac Lane showed connections between matroids and classical results in geometry. Specifically, he showed connections between matroids and the sets of points which lie on the lines of configurations such as the Desargues configuration and Pappus configuration in classical projective geometry (a geometry where no lines are parallel to each other). Because there are so many interesting examples of matroids, the theorems about general matroid structures have often been independently proved about these individual structures. This type of independent discovery has sometimes led to the questionable conclusion of independent rediscovery, which in no way is to take away from the impressive accomplishments of these individuals. Take for example, the case of Richard Rado (1906-1989).

The German born British mathematician Richard Rado did his work related to matroids in the context of transversals or systems of representatives for sets (defined in the next section). Rado wrote two doctoral theses in mathematics, the first in Germany (under I. Schur (1875-1941)) and the second in England (under G. H. Hardy (1877-1947)), where he fled because of his Jewish background when the Nazis came to power. Rado's contributions to matroids involve the lovely theorem of Philip Hall (also in the next section).

Another giant in the development of the theory of matroids was William Tutte, who died only very recently.

Tutte (1917-2002) led a distinguished career as a mathematician, but his role as a code breaker during World War II is less well known. Though he did not rediscover matroids as I have seen claimed (he credits Whitney's paper), he did certainly revitalize interest in matroids with his dramatic work.

Others who have made significant contributions (in a variety of ways) to the theory of matroids (in the broad sense) are Henry Crapo, Jack Edmunds, Gian-Carlo Rota, Neal Robertson (Ohio State University), and Paul Seymour (Princeton University). Rota (1932-1999), who spent much of his career at MIT, was never happy with the term matroids. He preferred the term combinatorial geometry because it pointed towards connections with geometric configurations in a non-metric environment.

In a previous section we discussed how the columns of a matrix give rise to a matroid by taking as the independent sets I of the matroid the columns that were linearly independent over a field F. Such a matroid is said to be representable over the field F. Rota emphasized the importance of trying to resolve one particular conjecture about matroids. This major avenue of investigation, which was already raised by Whitney, is whether or not any matroid is representable over some field F. This question is still an unsolved problem.

Related questions are:

* Which matroids are representable over every field?

* Which matroids are representable over the field with 2 elements? Such matroids are known as binary matroids.

* Which matroids are representable over the field with 3 elements? Such matroids are known as ternary matroids.

Suppose one takes a set of two elements E, where the elements of E are a and b. Consider two independence structures:

I₁ consisting of the null set and a
I₂ consisting of the null set and b.

Though these matroids have different sets of independent sets specified from the set E, they look structurally alike. Hence, as we have seen in other mathematical environments, we will not consider these as two different matroids but rather say they define isomorphic matroids. Can you verify for yourself that there are 4 non-isomorphic matroids that can be defined on the set E having two elements? It turns out there are 8 non-isomorphic matroids on a 3-element set and 17 non-isomorphic matroids on a 4-element set. For an 8-element set the number rises to 1724. Many open questions concerning matroids involve counting the number of non-isomorphic matroids of different kinds (binary, transversal, etc.).