• {ei} in F for each i,


• if G is in F, and if H is a non-empty subset of G, then H is in F.


• for each S that is a subset of E, if G and H are two members of F contained in S and maximal with this property, then |G|=|H|.

A matroid is a combinatorial object, introduced by Hassler Whitney in 1935, generalizing the notion of linear independence from linear algebra. Despite their relatively simple definition and humble motivations, they prove to be an incredibly versatile object for the modern combinatorialist, having deep relations with linear algebra, graph theory, and geometry, and finding applications in still other fields like topology, combinatorial optimization, coding theory, and even model theory.

A small caveat lector. As a consequence of the many ways to view a matroid, there are many names for the many different parts. Most of the things occurring in this writeup occur at most once, and are not required to understand what follows them.

Basic Definitions

One definition of a matroid M is a pair (E, I) consisting of a (finite!) set E and a collection I of subsets of E satisfying

• the empty set Ø ∈ I;
• if X ∈ I and Y ⊆ X, then Y ∈ I (subset-closure);
• if X,Y ∈ I and |X| > |Y|, then there exists e ∈ X - Y such that Y ∪ {e} ∈ I (exchange property).

E is called the ground set of M and the sets in I are called independent. Minimal dependent subsets of E, that is, dependent subsets whose every proper subset is independent, are called circuits. Maximal independent sets are called bases—by the exchange property, these are precisely the independent sets of maximal size. The rank of X ⊆ E is r(X) = max{ |I| : I ⊆ X and I ∈ I }. The closure cl(X) of X ⊆ E is the maximal subset X' ⊆ E containing X that has the same rank as X. A flat is an X ⊆ E such that X = cl(X).

The first very curious property of matroids is that they are determined by their circuits, or by their bases, or by their rank functions r : 2^E → N, etc. so the axioms for those objects can be taken as the definition of matroid instead. An appendix by Brylawski in the Theory of Matroids encyclopedia lists no less than 19 different axiomatizations of a matroid by its various facets. These relationships between superficially inequivalent definitions are called cryptomorphisms, and give matroid theorists a rich variety of ways of viewing the same object. Flats, for instance, are intimately connected with finite geometry, while the rank function acts much like the linear-algebraic notion of dimension, and circuits act much like circuits (that is, 2-regular connected subgraphs) in graphs.

The second enticing thing about matroids is their notions of minors and duality. The dual M* of a matroid M = (E, I) is the pair (E, I*) where I* = { I* ⊆ E : r(E - I*) = r(E) } is the collection of coindependent sets of M, that is, sets whose complement contains a basis. The circuits of M* are called cocircuits of M, the rank of a subset X in the dual is the corank r*(X) of X in M, and so on. As might be expected from the name, M** = M. Now, if e ∈ E, then M delete e is defined M\e = (E - {e}, I ∩ 2^E-{e})—that is, throw away e and only remember independence information about the remaining points—and M contract e is defined M/e = (M*\e)*. Any matroid that can be obtained by a sequence of contractions and deletions from M is called a minor of M. Minors and duality give matroids a lot of exploitable structure as algebraic objects, and also turn out to play nicely with natural classes of matroids, as we shall soon see.

Representable Matroids

Given a finite collection of vectors A from a vector space V over a field F, we construct the linear matroid M[A] in the obvious way: the ground set is the names of the vectors in A and the independent sets are the linearly independent sets. Typically A is considered as a matrix whose columns are the vectors. A matroid is F-representable if it is the linear matroid for some collection of vectors in some vector space over F. The bases of M[A] are those subsets of A which form bases for the vector space spanned by A, and the rank of X ⊆ A is exactly r(X) = dim_F span X. A matroid is called binary if it is GF(2)-representable, for GF(2) the finite field of order two, and it is regular if it is representable over every field.

For any field F, the class of F-representable matroids is closed under taking duals and minors. For any minor-closed class, it makes sense to talk of its excluded minors, that is, those matroids which do not belong to that class, while all their proper minors do. Due to a theorem of Bill Tutte, up to isomorphism—bijection of ground sets mapping independent sets to independent sets and vice versa—the only excluded minor of the binary matroids is the four-point line U₄², a matroid on a 4-element ground set whose independent sets are exactly the subsets with size at most 2—this is an example of a uniform matroid, U_n^r, defined similarly. Tutte also determined the excluded minors of the regular matroids: U₄², the Fano plane F₇ = M[ I₃ | A ], and its dual F₇* = M[ I₄ | A^T ], where I_n is the n×n identity matrix and A is the 3×4 matrix over GF(2) defined as

    / 0 1 1 1 \  
A = | 1 0 1 1 | .
    \ 1 1 0 1 /  

It is worth noting (1) that E(F₇) is exactly all the nonzero vectors in the vector space GF(2)³, which can be identified with the projective geometry GF(2)P² (referred to as PG(2,2) by matroid theorists), and (2) that since row operations and column permutation preserves the matroid arising from a matrix representation, every n-element F-representable matroid can be written in the form M[ I_r | X ] for an r×(n-r) matrix X over F, and then by row operations the dual can be represented M[ X^T | I_n-r ]. While it is known that representability in infinite fields have infinitely many excluded minors, it is conjectured by Rota that every finite field has a characterization in terms of finitely many excluded minors—the only fields for which we have these classifications are GF(2), GF(3), and GF(4). As of 2013, there is a reported proof of this conjecture, due to Geelen, Gerards, and Whittle; the proof has not yet been published, and is alleged to take years of writing.

Graphic Matroids

Given any graph G = (V, E), we can define its cycle matroid M(G) by taking as ground set the edge set E, and taking the circuits to be all the circuits in the graph; equivalently, a set of edges is independent if it forms a forest, that is, contains no circuits. A matroid is graphic if it is the cycle matroid of some graph. Graphic matroids are regular, with representation given by the V×E signed incidence matrix, obtained by arbitrarily orienting each edge in some direction, and saying the (v,e)-entry of this matrix is +1 if v is the head of e, -1 if it is the tail, and 0 if it is not incident. It turns out that matroid minors agree with the deletion-contraction minors of graphs exactly—M(G\e) = M(G)\e and M(G/e) = M(G)/e— so the graphic matroids are closed under minors.

The dual of a graphic matroid M(G), however, is not necessarily graphic, though if G is planar then the dual matroid M(G)* is the cycle matroid of the planar dual, M(G*). In fact, Whitney's planarity criterion states that a graph G is planar if and only if the matroid M(G)* is graphic. Given this and Kuratowski's theorem on planarity, it should be unsurprising that Tutte's excluded minors for the graphic matroids are the cographic matroids M(K₅)* and M(K_3,3)*, in addition to U₄², F₇, and F₇*.

Matroids extend graphs in many other ways. They have an interesting extremal theory paralleling extremal graph theory, including a parameter called covering number replacing the chromatic number in the Erdős–Stone type result which instead behaves more like the base-2 logarithm of chromatic number for graphs; and also their own version of Ramsey theory, which fueled the first Polymath project. Matroids also have a notion of connectivity which on the one hand involves itself with the facets of matroids which are useful in combinatorial optimization, and on the other hand provide the proper and natural setting for unorthodox graph theorems such as Tutte's Wheel Theorem for 3-connected graphs.

Other Ideas

Matroids are also an important object in combinatorial optimization. If one assigns weights to each element of a matroid and then tries to find the basis in a matroid with largest total weight, the naive greedy algorithm, which begins with the empty set Ø and repeatedly takes the element of largest weight among those which can be added to the current set while preserving independence, always gives the optimal result. The matroid axioms are in a precise sense exactly what is necessary for this to be the case. Kruskal's minimum spanning tree algorithm, for instance, is exactly the application of this greedy algorithm to the cycle matroid of a graph. Besides this connection, there are also operations called union, intersection, and partition for matroids which are able to describe many kinds of combinatorial optimization problems, and even better, have polynomial-time algorithms associated to them. Those who study the greedy algorithm have devised even more general objects, called greedoids, of which matroids are a special case, for examining their intimate relationship with the greedy algorithm more closely.

And this is, believe it or not, only scratching the surface. There are a number of good resources on matroids. Oxley's Matroid Theory is a standard text, and the two matroid encyclopedias by Neil White, Combinatorial Geometries and the previously mentioned Theory of Matroids, are also very good. Also notable is The Matroid Union, a research-level community blog run by and for matroid theorists.

Sources. This writeup is almost exclusively a product of my own memory, which in turn I obtained in a graduate-level mathematics course on matroids, so I can only cite my unpublished notes. Most (if not all) of this content should be contained in Oxley, however.