{"id":2239,"date":"2017-06-19T18:24:15","date_gmt":"2017-06-19T22:24:15","guid":{"rendered":"http:\/\/matroidunion.org\/?p=2239"},"modified":"2017-06-19T18:24:15","modified_gmt":"2017-06-19T22:24:15","slug":"the-template-theorem","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=2239","title":{"rendered":"The Template Theorem"},"content":{"rendered":"

Geelen, Gerards, and Whittle are still working on the write-up of their Herculean effort to build a matroid minor structure theory generalizing the work that Robertson and Seymour did for graphs. One of the consequences of their work has been published, namely a discussion of the highly connected members of a minor-closed class of matroids\u00a0[1<\/a>]. This work was mentioned by Peter in passing here<\/a> and in more detail here<\/a>. What Peter didn’t\u00a0talk about was the most detailed version of that structure theorem. Today I will do just that. To keep things light, I will focus on binary matroids, but [1] has results for matroids representable over any finite field.<\/p>\n

1. Low-rank perturbations<\/h2>\n

The key\u00a0concept is that of a\u00a0perturbation\u00a0<\/em>of a representable matroid. If $M = M[A]$,\u00a0and $T$ is a matrix with the same dimensions as $A$, then $M[A+T]$ is a\u00a0perturbation of $M$.\u00a0The hope is that, if we know a lot about $M$ and $T$ has low rank, then the resulting matroid still resembles $M$ to a large extent. We will study perturbations of\u00a0graphic matroids<\/em>, and start with a few examples. It will be convenient to drop the restriction that the perturbed matroid has the same size as $M$, and therefore we will allow the addition of a bounded number of elements.<\/p>\n

1.1 Adding a row<\/h3>\n

Let $A$ be the vertex-edge incidence matrix of a graph, and let $A’$ be the matrix obtained from $A$ by adding an arbitrary row. The matroid $M[A’]$ is known as an\u00a0even-cycle matroid.<\/em> It is an instance of the class of lift matroids frequently discussed on this blog, such as by Irene (here<\/a>,\u00a0\u00a0here<\/a>, and here<\/a>) and two weeks ago by Daryl (here<\/a>). Note that it can be obtained from $M$ by coextending the matroid by one element, and then deleting that element. They can be visualized by coloring the edges of the graph, calling an edge even<\/em> if its corresponding column in the matrix has a 0 in the new row, and\u00a0odd<\/em> if it has a 1.\u00a0This class of matroids is closed under minors.<\/p>\n

1.2 Adding a column<\/h3>\n

Let $A$\u00a0again be the vertex-edge incidence matrix of a graph, and this time let $A’$ be the matrix obtained from $A$ by adding an arbitrary column. The matroid $M[A’]$ will have one extra element, and is known as a\u00a0graft<\/em>. Grafts played a crucial role in the proofs of many fundamental\u00a0results in matroid theory, including Seymour’s Decomposition Theorem for\u00a0regular matroids [2]. They can be visualized by coloring the vertices of the graph\u00a0whose corresponding matrix row has a 1 in the new column.<\/p>\n

Note that the class of grafts is\u00a0not<\/em> closed under minors (contracting the graft element destroys the graphic structure). However, a closely related class, where we add an element to the graphic matroid\u00a0and<\/em> immediately contract that element, is closed under minors. The duals of these matroids are known as the\u00a0even cut matroids<\/em>. They have been extensively studied by Guenin, Pivotto, and Wollan (see, for instance, Irene’s PhD thesis [3<\/a>]).<\/p>\n

1.3 Adding a few elements to a low-rank flat<\/h3>\n

Let $G$ be a graph with $t$ distinguished vertices. We take the\u00a0vertex-edge incidence matrix, and add a few columns, but now these columns are only allowed to have nonzero entries corresponding to the $t$ distinguished vertices. The resulting class of matroids will resemble a graphic matroid everywhere but in a low-rank set. Note that this can be seen as a variation of the “adding a column” construction, but sometimes it is useful to consider the operation separately.<\/p>\n

2. Frame templates<\/h2>\n

Next, we ask ourselves what happens if we allow several of the\u00a0above operations in a row. Can there be fundamentally different ways to perturb a graphic matroid? Geelen, Gerards, and Whittle answered this question in full generality through the introduction of\u00a0templates.<\/em><\/p>\n

Definition.\u00a0<\/strong>A (binary)\u00a0<\/em>frame template is a tuple $\\Phi = (C, X, Y_0, Y_1, A_1, \\Delta, \\Lambda)$ with the following elements:
\n<\/em><\/p>\n

    \n
  1. Finite pairwise disjoint sets $C, X, Y_0, Y_1$;<\/em><\/li>\n
  2. A matrix $A_1$ with rows labeled by $X$ and columns labeled by $Y_0\\cup Y_1 \\cup C$;<\/em><\/li>\n
  3. A set\u00a0of row vectors $\\Delta$ closed under addition, with entries labeled by $Y_0 \\cup Y_1 \\cup C$;<\/em><\/li>\n
  4. A set\u00a0of column vectors $\\Lambda$ closed under addition, with entries labeled by $X$.<\/em><\/li>\n<\/ol>\n

    Definition.\u00a0<\/strong>A matrix $A’$ is said to\u00a0<\/em>respect\u00a0the template $\\Phi$ if it is of this form:<\/em><\/p>\n

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

    Here, a\u00a0<\/em>unit column is a column with exactly one nonzero. The incidence matrix and the columns labeled by $Z$ can be of arbitrary size.<\/em><\/p>\n

    Definition.\u00a0<\/strong>Let $A’$ be a matrix respecting the template $\\Phi$. Let $A$ be obtained from $A’$ by<\/em><\/p>\n

      \n
    1. Taking each column from $Z$ and adding to it some column labeled by an element of $Y_1$;<\/em><\/li>\n
    2. Deleting the columns labeled by $Y_1$;<\/em><\/li>\n
    3. Contracting the elements labeled by $C$ in the corresponding matroid.<\/em><\/li>\n<\/ol>\n

      Then $A$ and $M[A]$ are said to\u00a0<\/em>conform to\u00a0the template $\\Phi$.\u00a0<\/em><\/p>\n

      One should think about templates as recipes for constructing families of matroids.<\/p>\n

      Exercise.\u00a0<\/strong>Describe the examples from sections 1.1 – 1.3 using templates.<\/em><\/p>\n

      The main result from [1] is that templates can be used to describe all sufficiently large, sufficiently highly connected matroids in any minor-closed class. Highly connected means the following:<\/p>\n

      Definition.\u00a0<\/strong>A matroid $M$ is\u00a0<\/em>vertically $k$-connected if, for all separations $(X,Y)$ with $\\lambda(X) < k$, either $r(X) = r(M)$ or $r(Y) = r(M)$. In other words, one side of the separation is\u00a0<\/em>spanning.<\/p>\n

      The precise result is:<\/p>\n

      Theorem (Geelen, Gerards, Whittle [1]).\u00a0<\/strong>Let $\\mathcal{M}$ be a proper minor-closed class of binary matroids. There exist constants $k, l$ and frame templates $\\Phi_1, \\ldots, \\Phi_t, \\Psi_1, \\ldots, \\Psi_s$ such that:<\/em><\/p>\n

        \n
      1. Every matroid conforming to $\\Phi_i$ is in $\\mathcal{M}$ for $i = 1, \\ldots, t$;<\/em><\/li>\n
      2. Every matroid whose dual conforms to $\\Psi_j$ is in $\\mathcal{M}$ for $j = 1, \\ldots, s$;<\/em><\/li>\n
      3. For every vertically $k$ connected matroid $M \\in \\mathcal{M}$ with at least $l$ elements, there either exists an $i$ such that $M$ conforms to $\\Phi_i$ or a $j$ such that $M^*$ conforms to $\\Psi_j$.<\/em><\/li>\n<\/ol>\n

        The third property\u00a0says that the structure of the highly connected matroids in the class is completely described by a finite list of templates. The first two properties put some quite strict constraints on those templates:\u00a0any<\/em> matroid we can build using the template must be a member of the class!<\/p>\n

        The third property is reminiscent of the result by Robertson and Seymour that the “torsos” of a tree-decomposition are nearly-embeddable in some surface of bounded genus (see [4, Theorem 12.6.6<\/a>]). But in the graph minors theorem there is no analog of the converse: most graphs nearly-embeddable on that surface won’t be members of the class being studied.<\/p>\n

        The first two properties can be used to determine the full set of templates $\\Phi_1, \\ldots, \\Phi_t, \\Psi_1, \\ldots, \\Psi_s$ for a given class of matroids. I have worked on several such results with my PhD student Kevin Grace [5<\/a>, 6<\/a>]. For instance, let’s consider Seymour’s 1-flowing conjecture, discussed by Dillon here<\/a>. With Kevin I proved the following:<\/p>\n

        Theorem (Grace, vZ [5]).\u00a0<\/strong>There exist constants $k, l$ such that every vertically $k$-connected 1-flowing matroid on at least $l$ elements is either graphic or\u00a0cographic.\u00a0<\/em><\/p>\n

        In other words, any counterexample to Seymour’s conjecture will have to be small, or have a low-order vertical separation. The proof proceeds by considering an arbitrary frame template, and showing that it either has to be trivial, or it can be used to build an excluded minor for the class of 1-flowing matroids. In the process we develop some tools to help with proofs by induction on templates, and to clean up the matrix $A_1$, but those will have to wait for another day.<\/p>\n

        Other applications of templates include\u00a0growth rate<\/em> results, and finding sufficient sets of excluded minors to characterize the highly connected members of a minor-closed class of matroids.<\/p>\n

        References<\/h4>\n
          \n
        1. J. Geelen, B. Gerards and G. Whittle, The highly connected matroids in minor-closed classes<\/em>, Ann. Comb. 19 (2015), 107\u2013123.<\/li>\n
        2. P. D. Seymour,\u00a0Decomposition of regular matroids,\u00a0<\/em>J. Combin. Theory Ser. B 28(3) (1980), 305-359.<\/li>\n
        3. I. Pivotto,\u00a0Even Cycle and Even Cut Matroids.\u00a0<\/em>PhD Thesis, University of Waterloo (2011).<\/li>\n
        4. R. Diestel,\u00a0Graph Theory,\u00a0<\/em><\/em>Springer GTM 173, 5th edition (2016).<\/li>\n
        5. K. Grace, S. H. M. van Zwam,\u00a0Templates for Binary Matroids,\u00a0<\/i>SIAM J. Disc. Mathem. 31(1) (2017), 254 — 282.<\/li>\n
        6. K. Grace, S. H. M. van Zwam,\u00a0The highly connected even-cycle and even-cut matroids,\u00a0<\/i>Submitted (2016).<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

          Geelen, Gerards, and Whittle are still working on the write-up of their Herculean effort to build a matroid minor structure theory generalizing the work that Robertson and Seymour did for graphs. One of the consequences of their work has been … 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-2239","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2239","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=2239"}],"version-history":[{"count":4,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2239\/revisions"}],"predecessor-version":[{"id":2244,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2239\/revisions\/2244"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2239"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2239"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2239"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}