About

Matroids are an abstraction of several combinatorial objects, among them graphs and matrices. The word matroid was coined by Whitney in 1935 in his landmark paper “On the abstract properties of linear dependence”. In defining a matroid Whitney tried to capture the fundamental properties of dependence that are common to graphs and matrices.

Almost simultaneously, Birkhoff showed that a matroid can be interpreted as a geometric lattice. Maclane showed that matroids have a geometric representation in terms of points, lines, planes, dimension 3 spaces etc.

Often the term combinatorial geometry is used instead of simple matroids. However, combinatorial geometry has another meaning in mathematical literature. Rank 3 combinatorial geometries are frequently called linear spaces.

Matroids are a unifying concept in which some problems in graph theory, design theory, coding theory, and combinatorial optimization become simpler to understand.

These matroid pages have been on the web since 1995.

I am asked sometimes what a matroid is. I often revert to our sacred writings and recall the encounter of Alice with the grinning Cheshire cat. At one stage the cat vanishes away, beginning with the tip of its tail and ending with the grin, which persists long after the remainder of the cat. – W. T. Tutte