Reads everything but the room

i like math a lot. and of the different kinds of mathematics that i have acquainted myself with, matroids are my favourite mathematical object, bar none. so i'd like to teach you what a matroid is, one chost at a time.

i will try to make this course accessible to as many as i can. however, matroid theory is a graduate level topic in combinatorics and touches many fields. so to get the most out of this course, you should have a basic understanding of linear algebra, and it wouldn't hurt to know a bit of introductory graph theory or combinatorics either. if there is demand for it, i can put together little appendices to get you up to speed on these topics—leave me a comment or shoot me an ask!—but i'll try not to lean too heavily on things without citing them.

what are matroids?

matroids are a kind of finite geometrical object. they capture some geometrical information about a finite set of points, namely which of them lie together on lines, or on planes, or cetera. maybe these points are situated in some ambient space, but maybe not; this data can be taken down without making reference to that space. in this way, matroids are able to extract just the geometry of those points and nothing else, and this makes them extremely versatile objects that crop up all over the place in mathematics. and this is saying nothing of just how highly structured and rich in interesting data they are!

in 1935, hassler whitney defined matroids in order to study the linear independence of vectors in vector spaces. since then they have outgrown linear algebra to infect graph theory and projective geometry, dominate combinatorial optimization, fascinate algebraic geometers, confound enumerationists and logicians, and inspire computer scientists to study the greedy algorithm. they are a nexus at which many radically different kinds of mathematics intersect, and there are many ways to study them.

okay, that's enough motivation. let's get to it!

---

well, actually, two last bits of housekeeping, now that you're committed to reading. first, matroid theory has a lot of terminology, so as a convention i will be using bold text when i am defining a piece of terminology, and "quoted text" when i am giving a piece of terminology but NOT explicitly defining it.¹

second, i am not good with computer. so if mathml does a linebreak in the middle of some inline math then i'm sorry but i tried.²

rank functions

a matroid $\mathrm{M<!--\; -->}=<!--\; -->(<!--\; -->\mathrm{E<!--\; -->},<!--\; -->\mathrm{r<!--\; -->})<!--\; -->$ consists of a finite "ground set" $\mathrm{E<!--\; -->}$ and a rank function $\mathrm{r<!--\; -->}:<!--\; -->{\mathrm{2<!--\; -->}}^{\mathrm{E<!--\; -->}}\to <!--\; -->\mathrm{\mathbb{Z}<!--\; -->}$ that assigns integers called "ranks" to every subset of the ground set, satisfying the rank axioms, listed below:

1. "properness" – for all subsets $\mathrm{X<!--\; -->}\subseteq <!--\; -->\mathrm{E<!--\; -->}$,

   $$\mathrm{0<!--\; -->}\le <!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->\le <!--\; -->|<!--\; -->\mathrm{X<!--\; -->}|<!--\; -->\text{.<!-- -->}$$

2. "increasingness" – for all nested pairs of subsets $\mathrm{X<!--\; -->}\subseteq <!--\; -->\mathrm{Y<!--\; -->}\subseteq <!--\; -->\mathrm{E<!--\; -->}$,

   $$\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->\le <!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Y<!--\; -->})<!--\; -->\text{.<!-- -->}$$

3. "submodularity" — for all pairs of subsets $\mathrm{X<!--\; -->},<!--\; -->\mathrm{Y<!--\; -->}\subseteq <!--\; -->\mathrm{E<!--\; -->}$,

   $$\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->}\cup <!--\; -->\mathrm{Y<!--\; -->})<!--\; -->\le <!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->+<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Y<!--\; -->})<!--\; -->-<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->}\cap <!--\; -->\mathrm{Y<!--\; -->})<!--\; -->\text{.<!-- -->}$$

we'll say that the rank $\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{M<!--\; -->})<!--\; -->$ of the entire matroid $\mathrm{M<!--\; -->}$ is just the rank of the ground set $\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{E<!--\; -->})<!--\; -->$. this is kind of like the dimension of the matroid, but more on that later.

first, i'll gently remind you that $|<!--\; -->\mathrm{X<!--\; -->}|<!--\; -->$ is the cardinality of $\mathrm{X<!--\; -->}$, that is, the number of elements in it. we will only be dealing with finite sets, $|<!--\; -->\mathrm{X<!--\; -->}|<!--\; --><<!--\; -->\mathrm{\infty <!--\; -->}$. also, $\mathrm{X<!--\; -->}\cap <!--\; -->\mathrm{Y<!--\; -->}$ is the intersection of $\mathrm{X<!--\; -->}$ and $\mathrm{Y<!--\; -->}$, which is to say the elements common to both subsets, and $\mathrm{X<!--\; -->}\cup <!--\; -->\mathrm{Y<!--\; -->}$ is their union, the elements present in at least one of them.³

second, let's get a nice juicy example going. we'll see plenty more of these later but this one is famous so you gotta see it now. take the ground set $\mathrm{E<!--\; -->}(<!--\; -->{\mathrm{F<!--\; -->}}_{\mathrm{7<!--\; -->}})<!--\; -->=<!--\; -->\{<!--\; -->\mathrm{1<!--\; -->},<!--\; -->\mathrm{2<!--\; -->},<!--\; -->\mathrm{3<!--\; -->},<!--\; -->\mathrm{4<!--\; -->},<!--\; -->\mathrm{5<!--\; -->},<!--\; -->\mathrm{6<!--\; -->},<!--\; -->\mathrm{7<!--\; -->}\}<!--\; -->$ (or $\mathrm{1<!--\; -->}\mathrm{2<!--\; -->}\mathrm{3<!--\; -->}\mathrm{4<!--\; -->}\mathrm{5<!--\; -->}\mathrm{6<!--\; -->}\mathrm{7<!--\; -->}$ for short) and define a rank function by

$$\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->=<!--\; -->\{<!--\; -->\begin{array}{cc}|<!--\; -->\mathrm{X<!--\; -->}|<!--\; -->& \text{if <!-- -->}|<!--\; -->\mathrm{X<!--\; -->}|<!--\; -->\le <!--\; -->\mathrm{2<!--\; -->}\text{,<!-- -->}\\ \mathrm{2<!--\; -->}& \text{if <!-- -->}\mathrm{X<!--\; -->}\text{ is <!-- -->}\mathrm{1<!--\; -->}\mathrm{2<!--\; -->}\mathrm{3<!--\; -->}\text{, <!-- -->}\mathrm{1<!--\; -->}\mathrm{4<!--\; -->}\mathrm{5<!--\; -->}\text{, <!-- -->}\mathrm{1<!--\; -->}\mathrm{6<!--\; -->}\mathrm{7<!--\; -->}\text{, <!-- -->}\mathrm{2<!--\; -->}\mathrm{4<!--\; -->}\mathrm{6<!--\; -->}\text{, <!-- -->}\mathrm{2<!--\; -->}\mathrm{5<!--\; -->}\mathrm{7<!--\; -->}\text{, <!-- -->}\mathrm{3<!--\; -->}\mathrm{4<!--\; -->}\mathrm{7<!--\; -->}\text{, or <!-- -->}\mathrm{3<!--\; -->}\mathrm{5<!--\; -->}\mathrm{6<!--\; -->}\text{,<!-- -->}\\ \mathrm{3<!--\; -->}& \text{otherwise.<!-- -->}\end{array}$$

in other words, $\mathrm{r<!--\; -->}$ is as big as it can be for small subsets, but it caps out at $\mathrm{3<!--\; -->}$, and also there are some special triples (which you will soon learn are called "lines") that are capped even earlier at $\mathrm{2<!--\; -->}$. you can check that this satisfies the rank axioms—1 and 2 should be obvious, and for 3 essentially the only nonobvious computation is when $\mathrm{X<!--\; -->}$ and $\mathrm{Y<!--\; -->}$ are both lines—so this is indeed a matroid, of rank 3. this matroid ${\mathrm{F<!--\; -->}}_{\mathrm{7<!--\; -->}}$ is known as the Fano plane and you will see it again; this is not a threat, it is a promise.

finally, a quick nonexample of a matroid. let $\mathrm{E<!--\; -->}(<!--\; -->{\mathrm{P<!--\; -->}}_{\mathrm{3<!--\; -->}})<!--\; -->=<!--\; -->\{<!--\; -->\mathrm{a<!--\; -->},<!--\; -->\mathrm{b<!--\; -->},<!--\; -->\mathrm{c<!--\; -->}\}<!--\; -->$ be the edges of the path graph of length 3 and let $\mathrm{\nu <!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->$ be the "matching number" of the subgraph on the edges $\mathrm{X<!--\; -->}$: $\mathrm{\nu <!--\; -->}<!--\; -->(<!--\; -->\mathrm{\varnothing <!--\; -->})<!--\; -->=<!--\; -->\mathrm{0<!--\; -->}$, $\mathrm{\nu <!--\; -->}<!--\; -->(<!--\; -->\mathrm{a<!--\; -->}\mathrm{c<!--\; -->})<!--\; -->=<!--\; -->\mathrm{\nu <!--\; -->}<!--\; -->(<!--\; -->\mathrm{a<!--\; -->}\mathrm{b<!--\; -->}\mathrm{c<!--\; -->})<!--\; -->=<!--\; -->\mathrm{2<!--\; -->}$, and $\mathrm{\nu <!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->=<!--\; -->\mathrm{1<!--\; -->}$ otherwise. then the "necklace" ${\mathrm{N<!--\; -->}}_{\mathrm{3<!--\; -->}}=<!--\; -->(<!--\; -->\mathrm{E<!--\; -->}(<!--\; -->{\mathrm{P<!--\; -->}}_{\mathrm{3<!--\; -->}})<!--\; -->,<!--\; -->\mathrm{\nu <!--\; -->})<!--\; -->$ is not a matroid, as it fails submodularity:

$$\mathrm{\nu <!--\; -->}<!--\; -->(<!--\; -->\mathrm{a<!--\; -->}\mathrm{b<!--\; -->})<!--\; -->+<!--\; -->\mathrm{\nu <!--\; -->}<!--\; -->(<!--\; -->\mathrm{b<!--\; -->}\mathrm{c<!--\; -->})<!--\; -->-<!--\; -->\mathrm{\nu <!--\; -->}<!--\; -->(<!--\; -->\mathrm{b<!--\; -->})<!--\; -->=<!--\; -->\mathrm{1<!--\; -->}+<!--\; -->\mathrm{1<!--\; -->}-<!--\; -->\mathrm{1<!--\; -->}=<!--\; -->\mathrm{1<!--\; -->}\ngeqq <!--\; -->\mathrm{2<!--\; -->}=<!--\; -->\mathrm{\nu <!--\; -->}<!--\; -->(<!--\; -->\mathrm{a<!--\; -->}\mathrm{b<!--\; -->}\mathrm{c<!--\; -->})<!--\; -->\text{.<!-- -->}$$

the intuition

the intuitive slogan for rank is "rank = 1 + dimension", or more precisely, $\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->=<!--\; -->\mathrm{1<!--\; -->}+<!--\; -->dim<!--\; -->\mathrm{X<!--\; -->}$, for whatever it is that the "dimension of $\mathrm{X<!--\; -->}$" could mean.

the idea is, you need one element to specify a point, geometrically speaking, even though points are obviously zero-dimensional. likewise, straight lines are one-dimensional, but you need two distinct points to span a line. two dimensional planes can be spanned by three points, so long as they are non-colinear. and so on. so perhaps instead of clinging to dimensional terminology, let's say: points are rank 1, lines are rank 2, planes are rank 3, etc.

this highlight one big reason why we use rank and not dimension: because the empty set needs a rank of its own, below points, but there's no sensible dimension to assign it. except maybe $\mathrm{-1<!--\; -->}$, which is really an awful number to start counting upwards from. i'm not interested in getting into it any deeper than this, but if this reason is unsatisfying then i encourage you to keep this issue in the back of your mind as we continue, especially as we start to discuss loops and, later, projective geometry.

with this intuition in place, let's try to interpret the rank axioms intuitively:

1. if you have $\mathrm{n<!--\; -->}$ elements then they specify an object of dimension at most $\mathrm{n<!--\; -->}-<!--\; -->\mathrm{1<!--\; -->}$.
2. if you have some elements specifying an object, and then you add more elements to it, the dimension of the object specified must stay the same or increase; it can't go down.

so far so good. but submodularity is a bit tricky though:

3. if you have two intersecting objects $\mathrm{X<!--\; -->}$ and $\mathrm{Y<!--\; -->}$, then the space they jointly specify can have dimension at most $dim<!--\; -->\mathrm{X<!--\; -->}+<!--\; -->dim<!--\; -->\mathrm{Y<!--\; -->}-<!--\; -->dim<!--\; -->\mathrm{X<!--\; -->}\cap <!--\; -->\mathrm{Y<!--\; -->}$.

if $\mathrm{X<!--\; -->}$ and $\mathrm{Y<!--\; -->}$ have some intersection of dimension $dim<!--\; -->\mathrm{X<!--\; -->}\cap <!--\; -->\mathrm{Y<!--\; -->}$, then they definitely have to share those dimensions. so when you're considering the dimension of $\mathrm{X<!--\; -->}\cup <!--\; -->\mathrm{Y<!--\; -->}$ which is jointly spanned by $\mathrm{X<!--\; -->}$ and $\mathrm{Y<!--\; -->}$, you can only spend the dimensions of the intersection once, not twice.

i like to imagine this with an open book, representing two planes meeting at a line: $\mathrm{X<!--\; -->}$ and $\mathrm{Y<!--\; -->}$ are the two covers, intersecting at the spine, and jointly spanning the 3d space in which you are opening the book. the covers of the book are attached along the whole spine, so they can only unfold into 3d; you would have to cut the spine down to a single point of connection (or disconnect them entirely) if you wanted to splay the covers out into 4d. but you could also keep the book closed without destorying the spine, and it would only span 2d which is less dimensions than 3d. so submodularity permits the rank to be deficient.

i also like to think of it in terms of an equivalent formulation of submodularity, which is may be more or less intuitive for you:

$$\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->}\cap <!--\; -->\mathrm{Y<!--\; -->})<!--\; -->\le <!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->+<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Y<!--\; -->})<!--\; -->-<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->}\cup <!--\; -->\mathrm{Y<!--\; -->})<!--\; -->\text{.<!-- -->}$$

now it's more like, since the two covers of an open book jointly span 3d space, the spine cannot have too large of a dimension, since some of the dimensions of $\mathrm{X<!--\; -->}$ and $\mathrm{Y<!--\; -->}$ are busy jointly spanning $\mathrm{X<!--\; -->}\cup <!--\; -->\mathrm{Y<!--\; -->}$.

however, the dimension of the intersection could be strictly less than this bound implies, if $\mathrm{X<!--\; -->}$ and $\mathrm{Y<!--\; -->}$ fail to actually intersect each other enough. maybe one or both of $\mathrm{X<!--\; -->}$ and $\mathrm{Y<!--\; -->}$ have no points located on the spine at all, only strictly inside the covers. then their arrangement in $\mathrm{X<!--\; -->}\cup <!--\; -->\mathrm{Y<!--\; -->}$ is gesturing at an intersection—whose size matroid theorists might call the local connectivity $\mathrm{c<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->},<!--\; -->\mathrm{Y<!--\; -->})<!--\; -->=<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->+<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Y<!--\; -->})<!--\; -->-<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->}\cup <!--\; -->\mathrm{Y<!--\; -->})<!--\; -->$—that we don't have the points (in $\mathrm{X<!--\; -->}\cap <!--\; -->\mathrm{Y<!--\; -->}$) to articulate.

regardless of whether my intuitive exposition made any sense, the real trick of matroid theory is that these axioms are all it takes to impose a coherent notion of geometry on the ground set. if you have ranks that are proper, increasing, and submodular, then—matroid theorists claim—you have geometrical information. i have some more theory to do and terms to define in the following sections, and i hope that will clear some of this up, by giving you some terminological ground to stand on.

the lattice of flats

let's prove our first proposition about matroids.

proposition 1.1. every subset $\mathrm{X<!--\; -->}\subseteq <!--\; -->\mathrm{E<!--\; -->}$ is contained in a unique maximal superset $\stackrel{‾<!--\; -->}{\mathrm{X<!--\; -->}}\supseteq <!--\; -->\mathrm{X<!--\; -->}$ of equal rank.

okay, that statement was a little bit glib, can i get an action replay on that?⁴

proof of prop 1.1. suppose $\mathrm{Y<!--\; -->},<!--\; -->\mathrm{Z<!--\; -->}\supseteq <!--\; -->\mathrm{X<!--\; -->}$ are two distinct supersets of equal rank to $\mathrm{X<!--\; -->}$. first note that $\mathrm{Y<!--\; -->}\cap <!--\; -->\mathrm{Z<!--\; -->}\supseteq <!--\; -->\mathrm{X<!--\; -->}$, so since rank is increasing, $-<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->\ge <!--\; -->-<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Y<!--\; -->}\cap <!--\; -->\mathrm{Z<!--\; -->})<!--\; -->$. then, together with submodularity at $\mathrm{Y<!--\; -->}$ and $\mathrm{Z<!--\; -->}$, we see that

$$\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->\le <!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Y<!--\; -->}\cup <!--\; -->\mathrm{Z<!--\; -->})<!--\; -->\le <!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Y<!--\; -->})<!--\; -->+<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Z<!--\; -->})<!--\; -->-<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Y<!--\; -->}\cap <!--\; -->\mathrm{Z<!--\; -->})<!--\; -->\le <!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->+<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->-<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->=<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->\text{,<!-- -->}$$

which means all the inequalities $\le <!--\; -->$ were really equalities $=<!--\; -->$ and thus $\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{Y<!--\; -->}\cup <!--\; -->\mathrm{Z<!--\; -->})<!--\; -->=<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->$.

since $\mathrm{Y<!--\; -->}$ and $\mathrm{Z<!--\; -->}$ were arbitrary, this means that for any two supersets of $\mathrm{X<!--\; -->}$ of equal rank, their union is an even greater superset of equal rank. there are only finitely many supersets of $\mathrm{X<!--\; -->}$, as they are all subsets of $\mathrm{E<!--\; -->}$, so the union of all supersets of $\mathrm{X<!--\; -->}$ whose rank is $\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->$, will be the unique maximal superset of that rank. ∎

okay, whew, glad that's over. that was a pretty sneaky trick we pulled at the end: because you could combine any two supersets into a bigger superset that still fits the bill, you know that your maximal superset must be unique, as if it wasn't unique then it wouldn't even be maximal!⁵

now that we know this maximal superset is unique, let's name it: $\stackrel{‾<!--\; -->}{\mathrm{X<!--\; -->}}$ is the closure of $\mathrm{X<!--\; -->}$. and let's also say that $\mathrm{X<!--\; -->}$ spans $\stackrel{‾<!--\; -->}{\mathrm{X<!--\; -->}}$.

a flat is a set which is closed, i.e. equal to its own closure—$\mathrm{F<!--\; -->}=<!--\; -->\stackrel{‾<!--\; -->}{\mathrm{F<!--\; -->}}$. flats are special among subsets of matroids as they are "where the geometry is happening". let me explain by defining some more terminology: flats of rank 1 are called points, flats of rank 2 are called lines, flats of rank 3 are called planes, and flats of rank $\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{M<!--\; -->})<!--\; -->-<!--\; -->\mathrm{1<!--\; -->}$ are called hyperplanes. there's also a unique flat of rank 0, so it doesn't usually get a name, but its elements are called loops, and loops belong to every flat.

flats behave like you might expect from straight line geometry. most importantly, intersections of flats are again flats,⁶ so by considering their ranks you get a limited number of possible outcomes. for instance, if two lines meet, they are either equal (i.e. they are the same line), or they meet at a point, or they meet only at the loops (i.e. effectively not meeting at all, and literally so in a "loopless" matroid). if two planes meet, they are either the same plane, or they meet in a line, or in a point, or at the loops.

the union $\mathrm{F<!--\; -->}\cup <!--\; -->\mathrm{F<!--\; -->}\prime <!--\; -->$ of two flats might not be a flat. however, you can always take the closure afterwards, to get a flat called the join $\mathrm{F<!--\; -->}\stackrel{‾<!--\; -->}{\cup <!--\; -->}\mathrm{F<!--\; -->}\prime <!--\; -->=<!--\; -->\stackrel{‾<!--\; -->}{\mathrm{F<!--\; -->}\cup <!--\; -->\mathrm{F<!--\; -->}\prime <!--\; -->}$. it turns out the flats of a matroid form a "lattice" where the "meet" is $\cap <!--\; -->$ and the "join" is $\stackrel{‾<!--\; -->}{\cup <!--\; -->}$. i love lattices and have a long history of being unable to shut up about them, but i will mostly hold my tongue for now. there used to be a heavily algebraic school of combinatorics that studied matroids lattice-theoretically, and while they have been largely relegated to history, their work and ambitions remain influential, so it would be a disservice to skip it entirely, but we should see a little more modern matroid theory first.

matroid diagrams

to conclude this first lesson, let's use our flat terminology to draw pictures of matroids. to start, a very simple proposition.

proposition 1.2. $\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->=<!--\; -->\underset{\text{flat <!-- -->}\mathrm{F<!--\; -->}\supseteq <!--\; -->\mathrm{X<!--\; -->}}{min<!--\; -->}\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{F<!--\; -->})<!--\; -->$.

proof. $\stackrel{‾<!--\; -->}{\mathrm{X<!--\; -->}}$ is a flat and has the same rank as $\mathrm{X<!--\; -->}$. and by maximality, every other flat containing $\mathrm{X<!--\; -->}$ has a strictly larger rank. ∎

perhaps this seems so simple as to be boring, but this is an important way to reframe rank: to give you a matroid, it suffices to tell you just the flats and their ranks. and since we have such suggestively geometric names for flats of low rank, maybe you can already see the trick we will try to pull... we're gonna just draw matroids as configurations of points and lines and planes! and if we're clever with perspective or use other visualization tricks, maybe we can depict higher rank flats too.

check out the matroid diagrams above. all lines (straight or not) are flats of rank 2, and all triples of points not lying on a line are not rank 2. the planes of the rank 4 matroids are unshaded but i have made an effort to suggest their existence by shading lines, and annotated with the number of planes of maximum size.

of some interest is the rank-3 "non-pappian matroid", so called because it defies pappus' hexagon theorem, which states that if you tried to draw that matroid on paper then the three medial points will also be colinear. in matroid theoretic terms this theorem might be restated "the non-pappian matroid is not representable over the reals".⁷ we'll see more of this later in this series.

there is also an attempt at depicting the necklace in a diagrammatic way, to demonstrate that not every such diagram defines a matroid. it uses (and abuses) the convention that, to depict points of size $\ge <!--\; -->\mathrm{2<!--\; -->}$, you might draw them as an appropriate number of spots all touching each other, to indicate colocation. of course, this diagram is gibberish because it is not a matroid. but i think it's fun.

chestnut 1.3. recall the loops of a matroid are those elements $\mathrm{e<!--\; -->}\in <!--\; -->\stackrel{‾<!--\; -->}{\mathrm{\varnothing <!--\; -->}}$. where should you draw the loops in a matroid diagram?

next time

this chost is getting real long and i'm over time so i should wrap it up. next time we'll build some more examples of matroids, learn some more about matroid anatomy and taxonomy, and discuss the fascinating phenomenon of "cryptomorphism" through matroid axiomatizations. there are so so many ways to look at a matroid, and i can't wait to show them to you!

---

1. the distinction, to me, is that sometimes i will give a definition of a complicated thing and give names to a bunch of parts of it. the thing itself will definitely be in bold, because i am explaining it, but the parts may be bold or "quoted" depending on whether i think there is something worth explaining about them. so if you see some new word in bold, that means i am explaining it or about to explain it, but if you see it in quotation marks instead, that means you should not worry about knowing what it is

2. cohost simply has too many widths and i too strongly despise writing around a trillion displaymaths. this chost is long enough as it is and i have so much more to bloviate about. i don't know why @staff won't just give me a little mathjax. as a treat for posting so slowly and gently that i don't wear out the servers

3. if you didn't already know this stuff, then i admire your gumption in hoping to follow along, but i fear it will be an uphill battle for you. if you did already know this stuff then here's a free time-saving tip: you can skip⁸ that paragraph⁹ the next time you read this post

4. yes! unique... maximal... superset... of equal rank...! haha jk here you go:

   • "superset" just means larger set: $\mathrm{X<!--\; -->}\subseteq <!--\; -->\stackrel{‾<!--\; -->}{\mathrm{X<!--\; -->}}\subseteq <!--\; -->\mathrm{E<!--\; -->}$.
   • "superset of equal rank" means that despite being larger we're making sure the rank is the same: $\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\stackrel{‾<!--\; -->}{\mathrm{X<!--\; -->}})<!--\; -->=<!--\; -->\mathrm{r<!--\; -->}<!--\; -->(<!--\; -->\mathrm{X<!--\; -->})<!--\; -->$.
   • "maximal" means that we are taking something as large as possible, subject to the conditions. a maximal superset of equal rank means if you try to add in any more elements, the rank will change (and because rank functions are increasing, we know that the change that will occur won't be a decrease).
   • "unique" means that there's only one such maximal superset of equal rank. in our necklace nonexample ${\mathrm{N<!--\; -->}}_{\mathrm{3<!--\; -->}}$, the singleton set $\{<!--\; -->\mathrm{b<!--\; -->}\}<!--\; -->$ has two distinct maximal supersets of equal matching number, namely $\{<!--\; -->\mathrm{a<!--\; -->},<!--\; -->\mathrm{b<!--\; -->}\}<!--\; -->$ and $\{<!--\; -->\mathrm{b<!--\; -->},<!--\; -->\mathrm{c<!--\; -->}\}<!--\; -->$. this proposition says that will never happen in a matroid.

5. all this talk of maximal elements and proofs by contradiction is getting me a little zorny

6. exercise!

7. my professor used to joke that this is certainly the earliest theorem in matroid theory, as 340 BCE predates even the definition of matroids by over two thousand years! if you're reading this, jim 🍻 cheers

8. my favourite part of reading math is skipping the boring parts you know already. nobody ever puts anything interesting in there!! doing the exercises is for cowards

9. you can also skip these footnotes!¹⁰

10. i love me some footnote tomfoolery. unfortunately markdown automatically renumbers footnotes, so this first pit of snakes won't be numbered 4, 5, 6 (as authorially intended) without giving up the laziness of markdown. i have complained about this before and i will do so again