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 be a finite-dimensional vector space, and let’s think about the collection of all linearly independent sets of vectors in . This collection has certain structural properties as a collection of sets: (1) if and , then , (2) the empty set is always independent, and (3) if and are both in and , then there is some such that . These properties are all proven in linear algebra using the operations defining a vector space, but they are purely combinatorial properties when is thought of as a set system.
With that in mind, we define a matroid to be a pair where is a finite set, and is a nonempty collection of subsets of such that
- (hereditary property) if and , then ; and,
- (augmentation property) if and are both in and , then there some such that
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 and are both maximal independent sets (with respect to inclusion) in a matroid . By augmentation, if then there is some such that is independent. But this contradicts maximality of . By playing the same game with roles reversed, we can’t have either. So all the maximal independent sets of 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.