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 [1]. This work was mentioned by Peter in passing here and in more detail here. What Peter didn’t talk 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.

1. Low-rank perturbations

The key concept is that of a perturbation of a representable matroid. If $M = M[A]$, and $T$ is a matrix with the same dimensions as $A$, then $M[A+T]$ is a perturbation of $M$. The 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 graphic matroids, 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.

1.1 Adding a row

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 even-cycle matroid. It is an instance of the class of lift matroids frequently discussed on this blog, such as by Irene (here,  here, and here) and two weeks ago by Daryl (here). 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 if its corresponding column in the matrix has a 0 in the new row, and odd if it has a 1. This class of matroids is closed under minors.

1.2 Adding a column

Let $A$ again 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 graft. Grafts played a crucial role in the proofs of many fundamental results in matroid theory, including Seymour’s Decomposition Theorem for regular matroids [2]. They can be visualized by coloring the vertices of the graph whose corresponding matrix row has a 1 in the new column.

Note that the class of grafts is not 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 and immediately contract that element, is closed under minors. The duals of these matroids are known as the even cut matroids. They have been extensively studied by Guenin, Pivotto, and Wollan (see, for instance, Irene’s PhD thesis [3]).

1.3 Adding a few elements to a low-rank flat

Let $G$ be a graph with $t$ distinguished vertices. We take the vertex-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.

2. Frame templates

Next, we ask ourselves what happens if we allow several of the above 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 templates.

Definition. A (binary) frame template is a tuple $\Phi = (C, X, Y_0, Y_1, A_1, \Delta, \Lambda)$ with the following elements:

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

Definition. A matrix $A’$ is said to respect the template $\Phi$ if it is of this form:

Here, a unit column is a column with exactly one nonzero. The incidence matrix and the columns labeled by $Z$ can be of arbitrary size.

Definition. Let $A’$ be a matrix respecting the template $\Phi$. Let $A$ be obtained from $A’$ by

1. Taking each column from $Z$ and adding to it some column labeled by an element of $Y_1$;
2. Deleting the columns labeled by $Y_1$;
3. Contracting the elements labeled by $C$ in the corresponding matroid.

Then $A$ and $M[A]$ are said to conform to the template $\Phi$. 

One should think about templates as recipes for constructing families of matroids.

Exercise. Describe the examples from sections 1.1 – 1.3 using templates.

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:

Definition. A matroid $M$ is 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 spanning.

The precise result is:

Theorem (Geelen, Gerards, Whittle [1]). 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:

1. Every matroid conforming to $\Phi_i$ is in $\mathcal{M}$ for $i = 1, \ldots, t$;
2. Every matroid whose dual conforms to $\Psi_j$ is in $\mathcal{M}$ for $j = 1, \ldots, s$;
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$.

The third property says 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: any matroid we can build using the template must be a member of the class!

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]). 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.

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, 6]. For instance, let’s consider Seymour’s 1-flowing conjecture, discussed by Dillon here. With Kevin I proved the following:

Theorem (Grace, vZ [5]). There exist constants $k, l$ such that every vertically $k$-connected 1-flowing matroid on at least $l$ elements is either graphic or cographic. 

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.

Other applications of templates include growth rate results, and finding sufficient sets of excluded minors to characterize the highly connected members of a minor-closed class of matroids.

References

1. J. Geelen, B. Gerards and G. Whittle, The highly connected matroids in minor-closed classes, Ann. Comb. 19 (2015), 107–123.
2. P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28(3) (1980), 305-359.
3. I. Pivotto, Even Cycle and Even Cut Matroids. PhD Thesis, University of Waterloo (2011).
4. R. Diestel, Graph Theory, Springer GTM 173, 5th edition (2016).
5. K. Grace, S. H. M. van Zwam, Templates for Binary Matroids, SIAM J. Disc. Mathem. 31(1) (2017), 254 — 282.
6. K. Grace, S. H. M. van Zwam, The highly connected even-cycle and even-cut matroids, Submitted (2016).