{"id":146,"date":"2013-08-22T11:07:45","date_gmt":"2013-08-22T15:07:45","guid":{"rendered":"http:\/\/matroidunion.org\/?p=146"},"modified":"2013-09-30T12:19:53","modified_gmt":"2013-09-30T16:19:53","slug":"rotas-conjecture-proven","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=146","title":{"rendered":"Rota’s Conjecture proved!"},"content":{"rendered":"

The Twitterverse has been abuzz<\/a> recently with the news that Rota’s Conjecture has been proved by Jim Geelen, Bert Gerards, and Geoff Whittle! See press releases here<\/a> and here<\/a> (with an interview of Geoff at the bottom) and here<\/a>. This news was known, by word of mouth, to people in the community close to the sources for a while, but let me take this opportunity to try to explain to the non-experts what this conjecture is all about.\u00a0I will build up in a few steps from a small class of objects to bigger and bigger classes. For the experts, this survey by Geelen, Gerards, and Whittle<\/a>\u00a0might be better reading.<\/p>\n

1. Graphs<\/h1>\n

Kuratowski’s Theorem (or, more correctly, a variant proved by Wagner), states:<\/p>\n

Theorem 1.\u00a0<\/strong>A graph is planar if and only if it has no minor isomorphic to $K_5$ or $K_{3,3}$.<\/p>\n

A number of words need definition. A\u00a0graph<\/em> is a triple $(V, E, \\iota)$ where $V$ is a finite set, called the\u00a0vertices<\/em>, $E$ is a finite set, called the\u00a0edges<\/em>, and $\\iota: V\\times E \\to \\{0,1\\}$ is an\u00a0incidence relation<\/em>\u00a0<\/em>telling us which vertices meet which edges, with the rule that every edge meets exactly one or two vertices. Such structures are easily visualized as networks:<\/p>\n

\"Graph\"<\/a><\/p>\n

 <\/p>\n

A graph is\u00a0planar<\/em> if it can be drawn in the plane such that no two edges cross. The drawing above does not meet this criterion because edges $e_3$ and $e_4$ cross, but it is not hard to fix this, so the graph itself is planar.<\/p>\n

A\u00a0minor\u00a0<\/em>of a graph is obtained by doing a sequence of the following operations: delete an edge,\u00a0contract<\/em>\u00a0<\/em>an edge (this means deleting the edge and then identifying its two endpoints), or delete a vertex having no edges incident with it. Finally, the two graphs $K_5$ and $K_{3,3}$ are the following:<\/p>\n

\"kuratowski\"<\/a><\/p>\n

 <\/p>\n

We say $K_{5}$ and $K_{3,3}$ are the excluded minors<\/em> for the class of planar graphs.\u00a0Now Robertson and Seymour proved an amazing and vast generalization of this:<\/p>\n

Theorem 2.\u00a0<\/strong>Every minor-closed class of graphs can be characterized by a finite set of excluded minors.<\/em><\/p>\n

“Minor-closed” means that if a graph is in the class, then all its minors are as well. This was a work of epic proportions, spanning 23 papers and hundreds of pages.<\/p>\n

2. Binary matroids<\/h1>\n

Let $G$ be a graph, and consider the following matrix: label the rows by $V$, the columns by $E$, and an entry $A_{ve}$ is 1 if $v$ is incident with $e$ in $G$, and 0 otherwise. This is called the\u00a0incidence matrix<\/em>\u00a0<\/em>of $G$. For many reasons, instead of looking at the matrix by itself, we look at its\u00a0row space\u00a0<\/em>(i.e. every vector that can be obtained by taking linear combinations of the rows). Here we interpret the matrix over $\\text{GF}(2)$, i.e. the finite field with 2 elements (so $1+1 = 0$). Just like we wanted to distinguish planar graphs among all graphs, we want to distinguish row spaces of graphs among all row spaces:<\/p>\n

Problem.<\/strong>\u00a0Which row spaces can be obtained as the row space of the incidence matrix of a graph?<\/p>\n

The following classical result is due to Tutte:<\/p>\n

Theorem 3.\u00a0<\/strong>A row space over $\\text{GF}(2)$ is the row space of a graph if and only if it does not have any minor isomorphic to one of the following row spaces: $M^*(K_5)$, $M^*(K_{3,3})$, $F_7$, $F_7^*$.<\/em><\/p>\n

Again a finite list! Of course, I have to tell you what it means to have another row space as a minor. We now have only two operations, deletion and contraction.\u00a0Deletion<\/em> simply means deleting one coordinate from each vector in the row space (this corresponds to deleting a column from the original matrix).\u00a0Contraction<\/em> means that first we keep only the vectors that have a 0 in the specified coordinate, and then we delete that coordinate (in the matrix, we’d row-reduce the column so it has only one non-zero entry in the first row, and then we delete both that first row and the column). You can check that this corresponds to deletion and contraction in the graph.<\/p>\n

The row space $F_7$ is given by the following matrix:<\/p>\n

$$ \\begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 1\\\\ 0 & 1 & 0 & 1 & 0 & 1 & 1\\\\ 0 & 0 & 1 & 0 & 1 & 1 & 1\\end{bmatrix}$$<\/p>\n

Finally, the row spaces indicated with a star are the\u00a0orthogonal complements<\/em> of these row spaces.<\/p>\n

Note that Robertson and Seymour’s result does not help at all in the proof of Tutte’s theorem: the former talks only about minors inside the class of graphs, and Tutte’s theorem talks about minors just outside the class.<\/p>\n

Binary row spaces are a much bigger set of objects than graphs (see Peter’s posts for more precise statements). Nevertheless, Geelen, Gerards, and Whittle managed to prove an analogue of the Robertson-Seymour theorem:<\/p>\n

Theorem 4.\u00a0<\/strong>Every minor-closed class of binary row spaces can be characterized by a finite set of excluded minors.<\/em><\/p>\n

This (and the generalization discussed below) took them over a decade to prove, and they are currently working on a write-up, which they project will take another few years to complete.<\/p>\n

3. Matroids<\/h1>\n

To define a matroid, we again look at the row space slightly differently. Take a matrix generating the row space, and let $E$ be the set of columns. We say a subset of $E$ is\u00a0independent<\/em>\u00a0<\/em>if the corresponding column vectors are linearly independent, and it is\u00a0dependent<\/em> otherwise. Now we do something weird: we throw away all information about the vectors, and only keep the independence information. What we’re left with is an example of a\u00a0matroid.<\/em><\/p>\n

Definition.\u00a0<\/strong>A\u00a0matroid\u00a0<\/em>is a pair $(E, \\mathcal{I})$ where $E$ is a finite set and $\\mathcal{I}$ is a collection of subsets of $E$, called\u00a0independent sets<\/em>, that satisfy the following axioms:<\/p>\n

    \n
  1. $\\emptyset \\in \\mathcal{I}$;<\/li>\n
  2. If $X \\in \\mathcal{I}$ and $Y \\subseteq X$ then $Y \\in \\mathcal{I}$;<\/li>\n
  3. If $X, Y \\in \\mathcal{I}$ and $Y$ has more elements than $X$, then there exists $e\\in Y – X$ such that $X\\cup\\{e\\} \\in \\mathcal{I}$.<\/li>\n<\/ol>\n

    It is easily verified that these hold for the example defined in the first paragraph. But they don’t just hold for the row spaces over $\\text{GF}(2)$, they hold for any matrix! This prompts new terminology: a matroid is $\\mathbb{F}$-representable\u00a0<\/i>if there exists a matrix over the field $\\mathbb{F}$ whose columns satisfy the dependencies prescribed by the matroid. Now we’ve once again grown our collection of objects, and therefore we would like to identify the old objects inside the new collection. Tutte has done this for us:<\/p>\n

    Theorem 5.\u00a0<\/strong>A matroid is $\\text{GF}(2)$-representable if and only if it has no minor isomorphic to $U_{2,4}$.<\/em><\/p>\n

    Here $U_{2,4}$ is the matroid $(E, \\mathcal{I})$ where $E = \\{1,2,3,4\\}$ and $\\mathcal{I}$ consists of all subsets of size at most 2. The minor operation again generalizes the operations above:\u00a0deletion<\/em>\u00a0of $e$ means we restrict our matroid to $E – \\{e\\}$ and the independent sets to those not containing $e$.\u00a0Contraction<\/em> of $e$ means the same, but in addition we require keeping only those independent sets $X$ such that $X\\cup \\{e\\}$ was independent in the original matroid.<\/p>\n

    Now, at last, we have all ingredients to formulate<\/p>\n

    Rota’s Conjecture.\u00a0<\/strong>For every finite field $\\text{GF}(q)$, there is a finite set of excluded minors for the class of $\\text{GF}(q)$-representable matroids.<\/p>\n

    Besides the result for $q = 2$ mentioned above, the conjecture has been proved for $q = 3$ (in 1979) and $q = 4$ (in 2000). And now Geelen, Gerards, and Whittle have proved it, in one fell swoop, for all remaining finite fields. Note that the corresponding statement for infinite fields (say matrices over the real numbers) is false.<\/p>\n

    A major ingredient in their proof is the following result, an equivalent of Theorem 4 for any finite field:<\/p>\n

    Theorem 6.\u00a0<\/strong>For every finite field $\\text{GF}(q)$, every minor-closed class of $\\text{GF}(q)$-representable matroids has a finite set of $\\text{GF}(q)$-representable excluded minors.<\/p>\n

    Note that once again, this result (whose importance cannot be overstated, and whose proof is of an astounding complexity) talks only about matroids that are within<\/em> the class of $\\text{GF}(q)$-representable matroids; Rota’s Conjecture talks about matroids just outside that class. The major breakthrough that led to the proof of Rota’s Conjecture was an insight that allowed them to use the machinery they developed to prove Theorem 6 on a slightly broader class of matroids anyway.<\/p>\n

    I tried to keep this description short, and in doing so I have omitted many subtleties (to the point of making some false statements, in particular in the case of contraction, where I omitted degenerate cases). But the purpose was to give a flavor of Rota’s Conjecture, and I hope I succeeded in that.<\/p>\n

    For a thorough introduction to matroid theory I recommend the book by James Oxley<\/a>. For a survey of Geelen, Gerards, and Whittle’s work on matroid minors, see here<\/a>. The survey will also have references for all results I mentioned above. I’m sure that we will frequently return to the subject of Rota’s Conjecture in this blog, hopefully with a more technical account of the proof techniques.<\/p>\n

    Update 29\/08:\u00a0<\/strong>added link to University of Waterloo’s press release here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

    The Twitterverse has been abuzz recently with the news that Rota’s Conjecture has been proved by Jim Geelen, Bert Gerards, and Geoff Whittle! See press releases here and here (with an interview of Geoff at the bottom) and here. This … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-146","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/146","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=146"}],"version-history":[{"count":12,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/146\/revisions"}],"predecessor-version":[{"id":273,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/146\/revisions\/273"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}