Algebra and combinatorics are different viewpoints on how to put structure on a set of things. An algebraist looks at a set and sees a bunch of things she can smash together to produce other things (e.g. numbers can be added, cake ingredients can be mixed, delicious avocados can be bred.) A combinatorialist* looks at a set and sees a bunch of things xe can group together (“combine” if you will) in different ways (e.g. categories can be Venn diagrammed, cake ingredients separated into dry/wet/nonbinary sections, delicious avocados will be eaten too quickly to be combined with anything if your combinatorialist is anything like this humble author.)
Algebraists get extremely pumped about linear algebra. Anytime you see a group of algebraists (as in murder of crows) hanging out, you can be damn sure one of them is just itching to use some linear algebra. And it was just such a group that, long ago, was infiltrated by a collection of combinatorialists who perpetrated the greatest heist of mathematical history: the theft of linear algebra itself.
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 simply a list of ways to group together elements of
(what fancy-pants mathematicians call a set system). So instead of starting with algebraic operations, as an algebraist might, and deriving this structure, our combinatorial heisters decided to take these properties as axioms…
That is, let’s 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 — cause yeah, we stole the lingo too.)
Okay, you say, so this is a fun game, but what’s the point? Stay tuned…
*some combinatorist is getting really pissed off at me right now.