Following up on my first post on biased graph, this time I’m going to discuss some problems related to frame and lift matroids. Some of these problems have already been discussed in Jim Geelen’s intriguing post on framework matroids. Following Jim’s notation, I’ll denote by $FM(\Omega)$ and $LM(\Omega)$ respectively the frame and lift matroid of $\Omega$. As usual, $M(G)$ denotes the graphic matroid of a graph $G$.

I should first explain why the classes of frame and lift matroids are minor closed. Let’s define minor operations for biased graphs. Given a biased graph $\Omega=(G,\mathcal{B})$, we define the deletion of an edge $e$ as $\Omega \backslash e = (G \backslash e, \mathcal{B}’)$, where $\mathcal{B}’$ is the set of cycles in $\mathcal{B}$ not using $e$. Contraction is a little trickier to define. If $e$ is not a loop of $G$, then  $\Omega/e=(G/e,\mathcal{B}’)$, where $\mathcal{B}’$ is the set of cycles in $\{C-\{e\}:C \in \mathcal{B}\}$. If $e$ is a balanced loop of $\Omega$, then $\Omega/ e = \Omega \backslash e$. The fun part comes when $e$ is an unbalanced loop of $\Omega$ (at some vertex $v$): in this case $\Omega/ e=(G’,\mathcal{B}’)$, where $G’$ is obtained from $G$ by replacing every edge $vw$ with an unbalanced loop at $w$ (for $w \neq v$) and $\mathcal{B’}$ is obtained from $\mathcal{B}$ by adding all loops at $v$.

With this definition, $FM(\Omega) \backslash A / B=FM(\Omega \backslash A /B)$ (as proved in [Zas91]). Things are slightly different with lift matroids. Deletion still works, so $LM(\Omega) \backslash e= LM(\Omega \backslash e)$. For contractions we need to be a bit careful; if $e$ is not an unbalanced loop of $\Omega$, then $LM(\Omega) / e =LM(\Omega /e)$. However, if $e$ is an unbalanced loop then $LM(\Omega)/e = M(G\backslash e)$. These minor operations work so well that in fact all the subclasses of frame and lift matroids discussed in my last post are minor closed.

When dealing with minor closed classes of matroids it’s natural to ask whether the class has a finite list of excluded minors, and if so, what the excluded minors are. The amazing structure theorem for matroids representable over a finite field, by Geelen, Gerards and Whittle, implies that, for example, even cycle matroids and signed graphic matroids have a finite list of excluded minors (since these matroids are, respectively, binary and ternary). Outside of the implications of the Matroid Structure Theorem, almost nothing is known about excluded minors of classes of frame and lift matroids, not because of lack of trying, but because stepping “just outside” the class of graphic matroids everything becomes way more difficult. Still, since frame matroids and lift matroids arise from graphs I would put some money on the validity of the following conjectures.

Conjecture 1: The class of frame matroids has a finite number of excluded minors.

Conjecture 2: The class of lift matroids has a finite number of excluded minors.

These conjectures are extremely difficult to approach. The reason is that frame and lift matroids are not well behaved in terms of graphical representations. By that I mean that we may have very different-looking biased graphs $\Omega_1$ and $\Omega_2$ with, say, $FM(\Omega_1)=FM(\Omega_2)$. More on this later.

There is still hope for some other classes of frame and lift matroids. For example, Matt DeVos, Luis Goddyn, Dillon Mayhew and Gordon Royle proved the following.

Theorem 1: Any excluded minor for the class of bicircular matroids has less than 16 elements.

The proof of this theorem has yet to be published; the theorem should eventually include the complete list of excluded minors. So far there is a list of 27 excluded minors (of size up to 9 elements) and this list is believed to be complete, but there are still a few possible sizes to check. For size 11 and higher the number of matroids is just too big to be checked by a computer without some quite sophisticated ideas.

The proof of Theorem 1 was made possible by a complete description of the behaviour of graphs representing the same bicircular matroid. Basically, if $FM(G_1,\emptyset)=FM(G_2,\emptyset)$, then $G_1$ and $G_2$ are related by simple, very localised operations. See [Wag85], [CGW91] and [Neu02]. It seems natural that bicircular matroids should be better behaved than, say, signed graphic matroids. The reason is the following surprising result by Dan Slilaty in [Sli06].

Theorem 2: Let $\Omega$ be a 3-connected biased graph with no balanced loops. If $\Omega$ has three vertex-disjoint unbalanced cycles, at most one of which is a loop, then $\Omega$ is the only biased graph representation of $FM(\Omega)$.

Since bicircular matroids have only unbalanced cycles, either they have a unique representation or they have a very special structure. The equivalent of Theorem 2 for lift matroids is unfortunately false. For example, it is possible to construct even cycle matroids with two representations, each with as many disjoint unbalanced cycles as you like. However I do believe that lift matroids of biased graphs with no balanced cycles should be better behaved than the average lift matroid. Let $BL$ denote the class of lift matroids of biased graphs with no balanced cycles. This class is not minor closed, since contracting an unbalanced cycle in a lift matroid produces a graphic matroid. But the union of $BL$ and the class of graphic matroids is a minor closed class. Let $\bar{BL}$ denote this class. Then the analogue of Theorem 1 for lift matroids is the following.

Conjecture 3: The class $\bar{BL}$ has a finite list of excluded minors.

To solve Conjecture 3 we would need to solve the following.

Problem 1: Describe the relation between graphs $G_1$ and $G_2$ such that $LM(G_1, \emptyset)=LM(G_2,\emptyset)$.

I think that Problem 1 is more tractable than the analogous problems for other classes of lift matroids (like even cycle matroids). The reason may be stated in another conjecture.

Conjecture 4: There is a constant $c$ such that any $3$-connected matroid in $\bar{BL}$ has at most $c$ biased graph representations.

As far as I know, no one has worked on this class of matroids.

References

Guest post by Jim Geelen.

$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\cC}{\mathcal{C}}$ $\newcommand{\bF}{\mathbb{F}}$

Anyone who has given significant consideration to the classes of frame matroids and lifted graphic matroids will have been struck by their similarities. The point of this posting is that these classes can be unified in a way that might have significant algorithmic implications. We also prove an amazing result (Theorem 3) concerning representations of matroids in the unified class.

Graphic matroids

The class of graphic matroids is very well understood; for example, the set of excluded minors is known and there is a polynomial-time algorithm for recognizing whether a matroid, given by its rank oracle, is graphic.

There are two key parts to the recognition algorithm. First one needs an algorithm for testing whether a given binary matroid is graphic; see, for example, [BC80]. Second one needs to check, for a given matroid $M$ and graph $G$, whether $M=M(G)$. This second part is solved by the following beautiful result due to Seymour [Sey81].

Theorem 1: Let $M$ be a matroid and let $G$ be a loopless $2$-connected graph with $E(G)=E(M)$. Then $M=M(G)$ if and only if $r(M)\le |V(G)|-1$ and, for each vertex $v$ of $G$, the set of edges incident with $v$ in $G$ forms a cocircuit of $M$.

Bias graphs

In the following three short sections, I will review the frame matroid and the lift matroid associated with a bias graph. These objects were introduced by Zaslavsky [Zas91] and were discussed in Irene Pivotto’s post on August 26.

Let $\cC$ be a set of circuits in a graph $G$. A theta in $G$ is loopless $2$-connected subgraph $H$ with $|E(H)| = |V(H)|+1$. Thus, a theta has two special vertices connected by three internally-disjoint paths, and such graphs have exactly three circuits. We say that $\mathcal C$ has the theta-property if there is no theta in $G$ having exactly two of its three circuits in $\cC$. The pair $(G,\cC)$ is called a bias graph if $\cC$ has the theta-property.

Frame matroids

The frame matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $FM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and for each component of $G[I]$ has at most one circuit.

Zaslavsky showed that a matroid $M$ is a frame matroid if and only if there is a matroid $M’$ and a basis $B$ of $M’$ such that $M$ is a restriction of $M’$ and for each element $e\in E(M’)-B$, the unique circuit of $B\cup\{e\}$ contains at most two elements of $B$.

Lifts of graphic matroids

The lift matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $LM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and $G[I]$ contains at most one circuit. Any matroid that is the lift matroid of a bias graph is called a lifted graphic matroid.

Zaslavsky showed that a matroid $M$ is a lifted graphic matroid if and only if there is a matroid $M’$ an element $e\in E(M’)$ such that $M’\del e = M$ and
$M’\con e$ is graphic.

Combining the classes

Let us call a graph $G$ a framework for a matroid $M$ if

• $E(M) = E(G)$,
• $G$ is connected,
• $r(M)\le |V(G)|$, and
• for each vertex $v$ of $G$, the set of edges incident with $v$ is a cocircuit of $M$.

We will call $M$ a framework matroid if it admits a framework representation.

The definition of a framework is motivated by Theorem 1; it has the appealing property that it is constructive. Given a matroid $M$, via a rank oracle, and a graph $G$ one can readily check (in polynomial time) whether or not $G$ is a framework for $M$. This constructive property is in contrast with the following conjectures.

Conjecture 1: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=FM(G,\cC)$.

Conjecture 2: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=LM(G,\cC)$.

I further believe that the recognition problem is intractable for both the class of frame matroids and the class of lifted graphic matroids. In contrast, I think that one can recognize framework matroids.

Conjecture 3: There is a polynomial-time algorithm that, given a matroid $M$ via its rank oracle, determines whether $M$ is a framework matroid.

Technical details

Let us call a graph $G$ a weak framework for a matroid $M$ if

• $E(M) = E(G)$,
• $r(M)\le |V(G)|$,
• for each vertex $v$ of $G$, the set of edges incident with $v$ is the union of a collection of cocircuits of $M$ and a set of loops of $M$, and
• each loop of $M$ is a loop of $G$.

This weakened notion behaves nicely with respect to our three classes.

• If $G$ is a graph, the $G$ is a weak framework for $M(G)$.
• If $M$ is the frame matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.
• If $M$ is the lift matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.

Lemma 1: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $H$ is a subgraph of $G$, then $H$ is a weak framework of $M| E(H)$.

Proof. Note that for any edge $e$ of $G$, $G-e$ is a weak framework of $M-e$. Now consider a vertex $v$ of $G$ and let $X$ denote the set of edges incident with $v$. If there is a nonloop edge $e$ of $G$ that is incident with $v$, then there is a cocircuit $C^*$ of $M$ such that $e\in C^*\subseteq X$. Then $r(E(G-v)) \le r(E(G)) – 1 \le |V(G)|-1 = |V(G-v)|$. Hence $G-v$ is a weak framework of $M\del X$. Now the result follows by deleting the vertices $V(G)-V(H)$, in an appropriately chosen order, and then deleting the edges in $E(G[V(H)]) – E(H)$. $\Box$

Lemma 2: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, then $r(M)\ge |V(G)|-1$ and equality holds if and only if $M$ is the cycle matroid of $G$.

Proof. Order the vertices of $G$ in the order $(v_1,v_2,\ldots,v_n)$ such that, for each $i\ge 2$, the vertex $v_i$ has a neighbour among $\{v_1,\ldots,v_{i-1}\}$. The sets $E(G[\{v_1,v_2,\ldots,v_n\}]),\, E(G[\{v_1,v_2,\ldots,v_n\}]),\,\ldots, \,E(G[\{v_1\}])$ have strictly decreasing rank in $M$, so $r(M)\ge |V(G)|-1$.

Equality clearly holds when $M=M(G)$. Conversely suppose that equality holds. A routine variation on the proof of Lemma 1 proves that, for each subgraph $H$ of $G$, we have $r(E(H)) \le |V(H)|-1$. Then, by the first part of the proof, for each connected subgraph $H$ of $G$ we have $r(E(H)) = |V(H)|-1$. In particular, if $H$ is a circuit of $G$, then $E(H)$ is a circuit of $M$, and, if $H$ is a tree of $G$, then $E(H)$ is independent in $M$. Thus $M = M(G)$. $\Box$

The following result is an easy application of Lemmas 1 and 2.

Lemma 3: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $M$ is $3$-connected, then $G$ is $2$-connected.

Lemma 4: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, $M$ is $3$-connected, and $|E(M)|\ge 4$, then $M$ is a framework matroid.

Proof. We may assume that among all connected weak frameworks for $M$ we have chosen $G$ with as many loops as possible. Since $M$ has no loops, if $G$ is not itself a framework of $M$, then there is a vertex $v$ of $G$ such that the set $X$ of edges incident with $v$ is the union of at least two distinct cocircuits of $G$. By Lemma 1 and the fact that $M$ is simple, there is at most one loop at $v$. Choose a cocircuit $C^*\subseteq X$ so that $X-C^*$ contains no loop of $G$. Now define $G’$ by replacing each edge $e=vw$ of $X-C^*$ with a loop at $w$. Note that $G’$ is a weak framework of $M$ and, since $G$ is $2$-connected, $G’$ is connected. However, this contradicts our choice of $G$ and that completes the proof.$\Box$

This proves that:

Theorem 2: The class of framework matroids contains all $3$-connected frame matroids and all $3$-connected lifted graphic matroids.

Represented matroids

A matrix with at most two nonzero nonzero entries in each column is called a frame matrix. Let $A_1$ and $A_2$ be matrices over a field $\bF$ with a common set $E$ of column indices. We say that $A_1$ and $A_2$ are row equivalent if $A_1$ can be obtained from $A_2$ by elementary row operations.

Problem 1: Given as input a matrix $A$, decide whether $A$ is row equivalent to a frame matrix.

Note that, if a matrix $A$ is row-equivalent to a frame matrix, then $M(A)$ is a frame matroid.

Conjecture 4: There is a polynomial-time algorithm that solves Problem 1.

We say that $A_1$ and $A_2$ are projectively equivalent if $A_1$ is row equivalent to a matrix $A_3$ that can be obtained from $A_2$ by column scaling. A signed incidence matrix is a frame matrix with entries in $\{0,\pm 1\}$ such that each column sums to zero. A lift of a matrix is a matrix obtained by appending a new row. A lifted signed-incidence matrix is a lift of a signed-incidence matrix.

Problem 2: Given as input a matrix $A$, decide whether $A$ is projectively equivalent to a lifted signed-incidence matrix.

Note that, if a matrix $A$ is projectively equivalent to a lifted signed-incidence matrix, then $M(A)$ is a lift of a graphic matroid.

Conjecture 5: There is a polynomial-time algorithm that solves Problem 2.

The amazing theorem

Let $A\in \bF^{V\times E}$ be a frame matrix with no all-zero column. The support of $A$ is the graph $G=(V,E)$ such that a vertex $v\in V$ is incident with an edge $e\in E$ if and only if the $(v,e)$-entry of $A$ is nonzero. If $A$ is a signed-incidence matrix with support $G$, then we say that $A$ is a signed incidence matrix of $G$.

The following remarkable fact came out of discussions with Bert Gerards and Geoff Whittle.

Theorem 3: Let $A$ be a matrix and let $M=M(A)$ be a framework matroid with framework $G$. Then either

• $A$ is projectively equivalent to a lift of the signed-incidence matrix of $G$, or
• $A$ is row equivalent to a frame matrix whose support is $G$.

Proof. By Lemma 2, we may assume that $r(M) = |V(G)|$. For each cocircuit $C$ of $M$ there is a vector $v$ in the row space of $A$ whose support is $C$. Therefore there is a frame matrix $A’$ whose support is $G$ and whose row space is contained in the row space of $A$. Now $G$ is a weak framework for $M(A’)$, so the rank of $A’$ is either $|V(G)|$ or $|V(G)|-1$. If $A’$ has rank $|V(G)|$, then $A$ is row equivalent to the frame matrix $A’$, as required. Thus we may assume that $A’$ has rank $|V(G)|-1$. Then, by Lemma 2, $M(A’)= M(G)$ and hence $A’$ is projectively equivalent to the signed incidence matrix of $G$. Finally, since the row space of $A’$ is contained in the row space of $A$ and $rank(A) = rank(A’)+1$, $A$ is row equivalent to a lift of $A’$. $\Box$

Theorem 3 some interesting consequences; the first of these is a striking converse to Theorem 2.

Corollary 1: For any field $\bF$, if $M$ is an $\bF$-representable framework matroid, then $M$ is either a frame matroid or a lifted graphic matroid.

Corollary 2: If $M$ is a $3$-connected matroid that has a representation by a frame matrix, then every representation of $M$ is either row equivalent to a frame matrix or is projectively equivalent to a lifted signed incidence matrix.

Corollary 3: If $M$ is a $3$-connected matroid that has a representation by a lifted signed incidence matrix, then every representation of $M$ is either projectively equivalent to a lifted signed incidence matrix or is row equivalent to a frame matrix.

Consider, for example, the matroid $R_{10}$. It is represented over GF$(3)$ by the “unsigned” incidence matrix of $K_5$. However, over GF$(2)$ it is represented by a lift of a signed incidence matrix of $K_5$.

References

[BC80] R.E. Bixby, W.H. Cunningham, Converting linear programs to network problems, Math. Oper. Res. 5 (1980), 321-357.
[Sey81] P.D. Seymour, Recognizing graphic matroids, Combinatorica 1 (1981), 75-78.
[Zas91] T. Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory, Ser. B 51 (1991), 46-72.

$\newcommand{\cM}{\mathcal{M}}$

This entry continues on from my last, which concerns the growth rates of matroids in minor-closed classes. A one-line recap of my notation is that, if $\cM$ is a minor-closed class of matroids, then $h_{\cM}(n)$ denotes the ($\mathbb{Z} \cup \{\infty\}$)-valued function whose value at each integer $n$ is the maximum number of elements in a simple matroid in the class of rank at most $n$. Last time I finished with the growth rate theorem of Geelen, Kabell, Kung and Whittle – here it is again.

Growth Rate Theorem
Let $\cM$ be a minor-closed class of matroids. Either

1.  $h_{\cM}(n) \le c_{\cM}n$ for all $n$,
2. $\binom{n+1}{2} \le h_{\cM}(n) \le c_{\cM}n^2$ for all $n$, and $\cM$ contains all graphic matroids,
3. $\frac{q^n-1}{q-1} \le h_{\cM}(n) \le c_{\cM}q^n$ for all $n \ge 2$ and some prime power $q$, and $\cM$ contains all GF$(q)$-representable matroids, or
4. $h_{\cM}(n) = \infty$ for all $n \ge 2$, and $\cM$ contains all simple rank-$2$ matroids.

This is surprising – up to a constant factor, the growth rate function for an arbitrary minor-closed class has just four possible types and, if the class has superlinear growth rate function then the function is `explained’ by the class containing a natural class with which its growth rate function agrees asymptotically. In this entry and the next, we’ll discuss some questions related to this theorem, starting with the scariest.

Structure

Thinking as we did with Mader’s theorem (Theorem 1 in my last entry), the burning question is why growth rate functions are restricted in this way. In the case of graphs, growth rate functions are controlled because of the structure guaranteed by the graph minors structure theorem. For this purpose, we can only really hope to describe classes satisfying outcomes 1-3 of the theorem, so we exclude some rank-$2$ uniform matroid to gain traction, and pose the following question:

Problem 1: Given an integer $n$, find a structural description for minor-closed classes of matroids not containing $U_{2,n}$.

An solution to this problem would yield a theorem that implies the growth rate theorem (and much more) very easily.

This problem is probably extremely difficult in general, but the case where the matroids are representable over a fixed finite field GF($q$) has been solved. As a major part of their work on the recently vanquished Rota’s Conjecture, Geelen, Gerards and Whittle have proved (but unfortunately not quite written yet – see [GGW07]) a structure theorem for the matroids in arbitrary minor-closed class of GF$(q)$-representable matroids. The representable case of the growth rate theorem falls out of their theorem without much effort.

However, the non-representable case has genuine difficulties not arising from representable matroids that make a structure theorem much harder to dream up. Spikes, for example, cause a special type of trouble that doesn’t crop up over finite fields (see [G08] for a discussion). Problem 1 in its full generality is still very much open.

Zooming In

Something that seems more approachable is to ask more exact questions about how growth rate functions behave. It is one thing to know that $h_{\cM}(n)$ is bounded above and below by, say, a quadratic in $n$, but it is another thing to know the asymptotic or exact behaviour of the function itself. In some cases, this is trivial; there are no prizes for working out the answer if $\cM$ is the class of graphic matroids, for example. In some cases, it seems very hard – even the class of graphic matroids with no $M(K_t)$-minor for general $t$ has a growth rate function that is only partially understood (it is a linear function whose gradient is known asymptotically in $t$, but not known for any fixed $t > 9$ (edit: corrected – thanks Jim), see Thomason [T01]).

However, for many specific classes, the problem is interesting and some results are known. Kung, Mayhew, Pivotto and Royle [KMPR13] recently showed that the growth rate function for the binary matroids with no AG$(3,2)$-minor is the same as that of the graphic matroids for all $n \ge 5$. Geelen and I [GN10] showed that, for sufficiently large $n$, the growth rate function for the class of matroids with no $U_{2,\ell+2}$-minor is equal to that of the GF$(q)$-representable matroids, where $q$ is the largest prime power not exceeding $\ell$. We also have shown, (and will write someday) that every minor-closed class $\cM$ whose growth rate function is exponential in $n$ satisfies $h_{\cM}(n) = \frac{q^{n+k}-1}{q-1} – qd$ for all sufficiently large $n$, where $k$ and $d$ are nonnegative integers with $d \le \frac{q^{2k}-1}{q^2-1}$.

Many questions of this sort are still open. Here is one in quite a general form:

Problem 2: Let $\mathfrak{F}$ be a set of fields containing at least one finite field, and $\cM$ be the class of matroids representable over all fields in $\mathfrak{F}$. Determine $h_{\cM}(n)$.

This determination could be asymptotic, exact, or exact for all large $n$. Some cases are easy; if $\mathfrak{F}$ contains GF$(2)$ then it is either the class of binary matroids or regular matroids. If $\mathfrak{F}$ contains GF$(3)$ then the answer will follow from Whittle’s characterisation of ternary matroids [W97]. If all fields in $\mathfrak{F}$ share a common subfield that is not itself in $\mathfrak{F}$, then $\cM$ has exponential growth rate function and the (eventually exact) answer probably follows from our theorem above. If $\mathfrak{F} = \{\mathrm{GF}(4), \mathrm{GF}(5)\}$ then $\cM$ is the class of golden-mean matroids and there is a conjectured answer of Archer [A05] confirmed in some cases by Welsh [W11]. The case where $\mathfrak{F}$ contains $\mathbb{C}$ and one other field GF$(q)$ is very interesting and the extremal examples are probably all Dowling geometries over GF$(q)$. Here is a concrete conjecture to that effect:

Conjecture 1: Let $q$ be a prime power. The class $\cM$ of matroids representable over $\mathbb{C}$ and GF$(q)$ has growth rate function $h_{\cM}(n) = n + (q-1)\binom{n}{2}$ for all sufficiently large $n$.

One could modify this conjecture to the case where $\cM$ is the class of $\mathbb{C}$-representable matroids with no $U_{2,t}$-minor for some integer $t \ge 4$. In this case, the extremal examples are still probably the Dowling geometries, but again not much is known.

Next time, we’ll talk about generalisations of $h_{\cM}(n)$ applying to classes that do contain all simple rank-$2$ matroids. See you then.

References

[A05] S. Archer. Near varieties and extremal matroids, PhD thesis, Victoria University of Wellington, 2005.

[G08] J. Geelen. Some open problems on excluding a uniform matroids. Adv. in Appl. Math. 41(4):628-637, 2008.

[GGW07] J. Geelen, B. Gerards, G. Whittle. Towards a matroid-minor structure theory. In Combinatorics, complexity and chance, vol. 34 of Oxford Lecture Ser. Math. Applic. 72-92. Oxford Univ. Press, Oxford, 2007.

[GN10] J. Geelen, P. Nelson. The number of points in a matroid with no $n$-point line as a minor. J. Combin. Theory Ser. B, 100(6):625-630, 2010

[KMPR13] J. Kung, D. Mayhew, I. Pivotto, G. Royle. Maximum size binary matroids with no AG(3,2)-minor are graphic. arXiv:1304.2448 [math.CO]

[T01] A. Thomason. The extremal function for complete minors. J. Combin. Theory Ser.B 81:318-338, 2001

[W11] M. Welsh. Golden mean and secret sharing matroids. Master’s thesis, Victoria University of Wellington, 2011.

[W97] G. Whittle. On matroids representable over GF(3) and other fields. Trans. Amer. Math. Soc., 349(2):579-603, 1997