Jim Geelen, Bert Gerards, and Geoff Whittle Solved Rota’s Conjecture on Matroids

gcrota

Gian Carlo Rota

Rota’s conjecture

I just saw in the Notices of the AMS a paper by Geelen, Gerards, and Whittle where they announce and give a high level description of their recent proof of Rota’s conjecture. The 1970 conjecture asserts that for every finite field, the class of matroids representable over the field can be described by a finite list of forbidden minors. This was proved by William Tutte in 1938 for binary matroids (namely those representable over the field of two elements). For binary matroids Tutte found a single forbidden minor.  The ternary case was settled by by Bixby and by Seymour in the late 70s (four forbidden minors).  Geelen, Gerards and Kapoor proved recently that there are seven forbidden minors over a field of four elements.  The notices paper gives an excellent self-contained introduction to the conjecture.

This is a project that started in 1999 and it will probably take a couple more years to complete writing the proof. It relies on ideas from the Robertson-Seymour forbidden minor theorem for graphs. Congratulations to Jim, Bert, and Geoff!

Well, looking around I saw that this was announced in August 22′s post in a very nice group blog devoted by matroids- Matroid Union, with contributions by Dillon Mayhew, Stefan van Zwam, Peter Nelson, and Irene Pivotto. August 22? you may ask, yes! August 22, 2013. I missed the news by almost a year. It was reported also here and here  and here, and here, and here, and here!

This is a good opportunity to mention two additional conjectures by Gian-Carlo Rota. But let me ask you, dear readers, before that a little question.

Rota’s unimodality conjecture and June Huh’s work

Rota’s unimodality conjecture predicts that the coefficients of the characteristic polynomial of a matroid form a log-concave sequence. This implies that the coefficients are unimodal. A special case of the conjecture is an earlier famous conjecture (by Read) asserting that the coefficients of the chromatic polynomial of a graph are unimodal (and log-concave). This conjecture about matroids was made also around the same time by Heron and Welsh.

June Huh proved Reads’ unimodality conjecture for graphs and the more general Heron-Rota-Welsh conjecture for representable matroids for characteristic 0. Later Huh and  Eric Katz proved the case of  representable matroids for arbitrary characteristics. I already mentioned these startling results earlier and we may come back to them later.

Huh’s path to mathematics was quite amazing. He wanted to be a science-writer and accomponied Hironaka on whom he planned to write. Hironaka introduced him to mathematics in general and to algebraic geometry and this led June to study mathematics and a few years later to use deep connections between algebraic geometry and combinatorics to prove the conjecture.

Rota’s basis conjecture

Rota’s basis conjecture from the late 80′s appears to remain wide open. The problem first appeared in print in a paper by Rosa Huang and Rota. Here is a post about it also from “the matroid union.” It is the first problem in Rota’s article entitled “Ten Mathematics problems I will never solve“. Having access only to page one of the paper I can only guess what the other nine problems might be.

rota-fan

Rota’s portrait by Fan Chung Graham

 

 

About these ads
This entry was posted in Combinatorics, Open problems, Updates and tagged , , , , , , . Bookmark the permalink.

6 Responses to Jim Geelen, Bert Gerards, and Geoff Whittle Solved Rota’s Conjecture on Matroids

  1. Tony Huynh says:

    Minor Correction: As far as I understand it, the proof of Rota’s Conjecture will not rely on the Robertson-Seymour Graph Minor Theorem. It strongly borrows techniques from the Graph Minors papers, but strictly speaking, I do not think the Graph Minor Theorem will be used as an intermediate lemma along the way.

    • Gil Kalai says:

      Dear Tony, Thanks! I will clarify.

    • Bert Gerards says:

      Our proof of Rota’s conjecture relies on: (1) Our Matroid Minor Structure Theorem describing the structure of any minor closed class of matroids representable over a finite field, and a consequence of tha the WQO of matroids over a finite field. (2) The results on inequivalence of representations as described in section 6 of the Notices paper. The results under (2) do not rely on the Graph Minors Project. The results indicated under (1) extend the graph minors project but also do not rely on it. Our Matroid Minors Project does take the same structural perspective and line of thought as the Graph Minors Project, and in that sense we borrow from that, or better built on that. But we do not use any graph minor result as such; because we couldn’t: we had to rebuilt the entire theory from scratch, including its intersection with Graph Minors Project (so that is when the matroid is graphic).

      The major part of our proof of Rota’s conjecture is the Matroid Minors Structure Theorem.
      It is of significant interest in itself.

  2. kazekkurz says:

    Small mistake under the picture description Rora -> Rota.

    Corrected, thanks!

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