Introduction to Matroids

I like to think of  algebra and combinatorics as being different viewpoints on how to put structure on a set. In algebra, you add structure to a set by defining an operation on the set satisfying some desired properties. In combinatorics, on the other hand, you add structure to a set by defining a collection of its subsets satisfying some desired properties. This is an oversimplification of course, but it’s a useful rule of thumb, and is a nice way to think of matroids: they are the objects you get when you try to place a vector space structure on a set using the combinatorial viewpoint of what “structure” is. (Any number of people are annoyed with me right now: there are lots of other ways to think of matroids. I happen to like this one.)

The story goes like this. Let $V$ be a finite-dimensional vector space, and let’s think about the collection $\mathcal{I}$ of all linearly independent sets of vectors in $V$. This collection has certain structural properties as a collection of sets: (1) if $A \in \mathcal{I}$ and $B \subseteq A$, then $B \in \mathcal{I}$, (2) the empty set is always independent, and (3) if $A$ and $B$ are both in $\mathcal{I}$ and $|A| < |B|$, then there is some $v \in B$ such that $A \cup v \in \mathcal{I}$. These properties are all proven in linear algebra using the operations defining a vector space, but they are purely combinatorial properties when $\mathcal{I}$ is thought of as a set system.

With that in mind, we define a matroid to be a pair $M = (E,\mathcal{F})$ where $E$ is a finite set, and $\mathcal{F}$ is a nonempty collection of subsets of $E$ such that

1. (hereditary property) if $A \in \mathcal{F}$ and $B \subseteq A$, then $B \in \mathcal{F}$; and,
2. (augmentation property) if $A$ and $B$ are both in $\mathcal{F}$ and $|A| < |B|$, then there some $v \in B \setminus A$ such that $A \cup v \in \mathcal{F}$

It turns out that this is enough to recover many of the theorems we expect to be true of a collection of linearly independent sets. For example, suppose $A$ and $B$ are both maximal independent sets (with respect to inclusion) in a matroid $M = (E,\mathcal{F})$. By augmentation, if $|B| > |A|$ then there is some $v \in B \setminus A$ such that $A \cup v$ is independent. But this contradicts maximality of $A$. By playing the same game with roles reversed, we can’t have $|A| > |B|$ either. So all the maximal independent sets of $M$ have the same size (and are usually called bases.) In fact, because of the hereditary property, the set of bases of a matroid completely determines the matroid.

Other notions of linear algebra can also be adapted to this context, and you can spend many happy hours studying matroids and can find them in the most unexpected of mathematical landscapes. But while matroids are genuinely fascinating creatures, they lack the flexibility to handle the kind of independence I’m particularly interested in — in fact there’s a way (which will be made somewhat more precise later) in which matroids are one-directional objects, and for some things you need to move in two or even three directions 🙂

So next time, we’ll move on to multimatroids.