Rota's excluded minors conjecture is one of a number of conjectures made by mathematician Gian-Carlo Rota. It is considered to be an important problem by some members of the structural combinatorics community. Rota conjectured in 1971 that, for every finite field, the family of matroids that can be represented over that field has finitely many excluded minors. A proof of the conjecture has been announced by Geelen, Gerards, and Whittle.
Contents
Statement of the conjecture
If
A minor of a matroid is another matroid formed by a sequence of two operations: deletion and contraction. In the case of points from a vector space, deleting a point is simply the removal of that point from
For representability over the real numbers, there are infinitely many forbidden minors. Rota's conjecture is that, for every finite field
Partial results
W. T. Tutte proved that the binary matroids (matroids representable over the field of two elements) have a single forbidden minor, the uniform matroid
A matroid is representable over the ternary field GF(3) if and only if it does not have one or more of the following four matroids as minors: a five-point line
There are seven forbidden minors for the matroids representable over GF(4). They are:
This result won the 2003 Fulkerson Prize for its authors Jim Geelen, A. M. H. Gerards, and A. Kapoor.
For GF(5), several forbidden minors on up to 12 elements are known, but it is not known whether the list is complete.
Reported proof
Geoff Whittle announced during a 2013 visit to the UK that he, Jim Geelen, and Bert Gerards have solved Rota's Conjecture. The collaboration involved intense visits where the researchers sat in a room together, all day every day, in front of a whiteboard. It will take them years to write up their research in its entirety and publish it. An outline of the proof has appeared in the Notices of the AMS.