Rota’s Conjecture Proven (Probably)!

Professor Geoff Whittle of Victoria University in New Zealand, Professor Jim Geelen and Professor Bert Gerards recently announced* that they have proven a famous conjecture of Gian-Carlo Rota which has been open for 40+ years.

What is Rota’s Conjecture?  It turns out to be something you could have learned in Linear Algebra!  Let’s briefly explain what it’s all about:

Let F be a field (for example, the real numbers) and let V be a vector space over F.  Now let E = \{ x_1, x_2, \dots, x_n \} be a finite set of vectors from V.  Let X be the collection of all subsets of E which are linearly independent.  Basic facts from Linear Algebra show that the pair of sets E and X have the following three properties:

  1. The empty set is in X.
  2. If A is in X (so A is a linearly independent set of vectors from E), and B is a subset of A, then B is also in X (because a subset of linearly independent vectors is still linearly independent).
  3. If A and B are both in X (so both are sets of linearly independent sets of vectors from E) and the number of elements of A is larger than that of B, then we can find at least one vector in A, call it v, so that B \cup \{v\} is also in X.  That is, we can find a vector in A so that when we add it to the set B, we still get a linearly independent subset.

A pair (E,X) which has properties 1, 2, and 3 is called a (finite) matroid.  The way we explained it, E was a set of vectors in a vector space and X was the set of linearly independent subsets of E.  But the three properties make sense even if we just know that E is a set and X a collection of subsets.  So the real definition of a matroid is a pair (E,X) which has properties 1, 2, and 3.

The idea we should keep in mind though is that a matroid is a generalization of the idea of linearly independent vectors.  Collections of linearly independent vectors give you matroids, but you can have new matroids which don’t come from linearly independent vectors.  The classic example of a matroid that usually doesn’t come from linearly independent vectors is the Fano Plane.

The Fano Plane (and a Matroid!) from Wikipedia

The Fano Plane (and a Matroid!) from Wikipedia

We call a matroid representable over the field F if we can find a vector space V defined over F and a set of vectors E so that the collection of linearly independent subsets of E exactly give our matroid.  Of course, if you change the field then you get different vector spaces and, hence, different possibilities for E.  So which matroids are representable over F depends on the field F.

Rota conjectured that if F is a finite field (like \mathbb{Z}_p for any prime number p), then there are only finitely many minor minimal** matroids which are not representable over F.  That is, if you pick your favorite finite field F (like \mathbb{Z}_3), then you can find all but finitely many matroids by looking at collections of linearly independent sets of vectors in vector spaces over F.

Since there are infinitely many finite fields and infinitely many matroids (and we don’t even know all the possible matroids!), it’s hard to prove such a conjecture.  Nevertheless, this is the conjecture that these mathematicans believe they’ve proven.  There is a nice article on Phys.org saying a bit more about them and their work.  There is also a nice video interview of Professor Whittle from a few years ago where he talks about his life as a mathematician:

You are probably wondering what happens if F is an infinite field (like our old friend the real numbers).  It turns out that Rota’s Conjecture is false when F is infinite!  This was proven by Valmos in a 1978 paper entitled “The Missing Axiom of Matroid Theory is Lost Forever” (Is there another math paper with such a hauntingly sad title?).

Update:  We inserted “minor minimal” in our statement of Rota’s Conjecture to make it mathematically correct.  While we put it in the ** footnote below, Stefan van Zwam’s comment shows that what we wrote clearly could cause some confusion.  And of course we heartily encourage you to go to the link he provided for the straight dope on Rota’s Conjecture!

* We put “probably” in the title because Whittle, Geelen, and Gerards have to finish writing up their results and have it refereed by other mathematicians.  It’s not really proven until it passes muster with other experts.

** Technically, Rota conjectured that there are finitely many “minor minimal” matroids which are not representable over F.

About these ads

2 thoughts on “Rota’s Conjecture Proven (Probably)!

  1. I stumbled across this post doing a Google search, and unfortunately your description of the conjecture is wrong. “Minor minimal” is an essential qualifier! For instance, take all binary matroids (i.e. those having a vector representation over $\mathbb{Z}_2$) that in addition have the Fano plane as a restriction. It is easy to find an infinite collection of such matroids, and each of them is only representable over a field $F$ if the characteristic of that field is 2.

    I recently prepared an explanation of the result, see here: http://matroidunion.org/?p=146

    • Stefan,

      Thanks for the comment and the clarification. We agree that minor minimal is essential! It was relegated to a footnote in the original post to make the explanation less technical, but clearly that caused more problems than it solved.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s