Matroid computation in SageMath: visualizations

This post is another installment in my series on matroid computation in SageMath [1], with older posts herehere, here, and here. As always, clicking the “Evaluate” buttons below will execute the code and return the answer (or, in today’s post, draw the picture). The various computations are linked, so execute them in the right order.

Last summer, Jayant Apte was selected to participate in the Google Summer of Code program. During the summer he extended SageMath’s matroid capabilities in two major ways.

  • Drawing geometric representations of rank-3 matroids
  • A more efficient minor test for binary matroids

The first of these has been part of Sage for a while; the second is awaiting review but should be included fairly soon.

Let’s get started with everyone’s favorite matroid.

That was easy! We can deal with parallel elements too:

Loops are no problem either:

Note that we resort to a slightly different method of display for large parallel classes. The point in the geometric representation will receive a label that is not an element of the matroid, and below the diagram it will state that this label actually represents a parallel class of elements.

The examples above were chosen because the default positioning algorithm gives a decent picture. Unfortunately, that is not always the case:

In these instances, the options of the show() method come in handy. To get a full list, type in your own session of SageMath, and hit the key. This will bring up the help page of the method (assuming you defined $M$ to be a matroid in an earlier command). We will go through these options one by one.

This is not bad, but we don’t need a curved line to draw this diagram. The solution is to specify a different basis, whose elements will be placed at the corners of a triangle:

Trying different bases is not going to help the Pappus matroid too much. In that case, after inspecting, for instance, M.circuit_closures(), we can come up with custom coordinates for the points. To tell Sage that we’re doing this, we add the option pos_method=1.

A second example, just because:

Our final option today deals with betweenness. In projective geometry this is a meaningless concept, of course, but in a concrete diagram it can matter whether we draw a line from $a$ through $b$ to $c$ or from $b$ through $a$ to $c$. In SageMath, we can specify this through the line_orders option. An example should make this clear.

We specify the order on the line $\{d,e,f\}$:

A slightly less contrived example is provided by $\textrm{AG}(2,3)$.

I prefer a rotational symmetry to the curved lines:

It’s not perfect (I’d like the curved lines to protrude out of the square), but it’s in the ballpark.

Note: after you have drawn a matroid, the options for drawing so are saved. So next time,

will produce the same graphic.

There are many ways in which the drawing routines can be improved. Options like color, aspect ratio, letting the user decide how to handle parallel elements, and functionality like saving plot information when you save a matroid, adding “nice” plots to the built-in library of matroids, special plots for Dowling geometries, plots for rank-4 matroids, and the list goes on. Interested? There’s another Google Summer of Code coming up soon!

[1] SageMath is now the official name of the Sage Mathematical Software System.

Non-unimodality of 2-polymatroids

Guest post by Thomas Savitsky

A $k$-polymatroid is a generalization of a matroid in which the rank of an element is allowed to exceed one, but cannot exceed $k$.

Definition 1.
Let $S$ be a finite set. Suppose $\rho : 2^S \to \mathbb{N}$ satisfies the following four conditions:

  • if $X, Y \subseteq S$, then $\rho(X \cap Y) + \rho(X \cup Y) \le \rho(X) + \rho(Y)$
  • if $X \subseteq Y \subseteq S$, then $\rho(X) \le \rho(Y)$ (monotone);
  • $\rho(\varnothing) = 0$ (normalized); and
  • $\rho(\{x\}) \le k$ for all $x \in S$.

Then $(\rho, S)$ is a $k$-polymatroid with rank function $\rho$ and ground set $S$.

So a matroid is a $1$-polymatroid. Here are a few examples of $2$-polymatroids.

  • If $(r_1, S)$, and $(r_2, S)$ are matroids, then $(r_1+r_2, S)$ is a $2$-polymatroid.
  • If $G = (V, E)$ is a graph, one may define a $2$-polymatroid $(\rho, E)$, where
    $\rho(X)$ equals the number of vertices incident to $X$.
  • Given an $m \times 2n$ matrix with entries in a field, one may define a representable $2$-polymatroid on $n$ elements by pairing up the columns in a obvious manner.

We became interested in $k$-polymatroids and thought it would be practical to have a catalog of the small ones at our disposal. We successfully adapted the canonical deletion
approach used by Mayhew and Royle (see [MR08]) to catalog matroids on nine elements to $2$-polymatroids. This first required developing a theory of single-element extensions of $k$-polymatroids. We then wrote code in the C programming language and interfaced with Brendan McKay’s nauty program and the igraph graph library. After a few days of execution time on a desktop computer, our program produced a catalog of all $2$-polymatroids, up to isomorphism, on at most seven elements.

By consulting our catalog, we produced Table 1, which lists the number of unlabeled $2$-polymatroids on the ground set $\{1, \ldots, n\}$ by rank.

Table 1: The number of unlabeled $2$-polymatroids.
rank $\backslash$ $n$ 0 1 2 3 4 5 6 7
0 1 1 1 1 1 1 1 1
1 1 2 3 4 5 6 7
2 1 4 10 21 39 68 112
3 2 12 49 172 573 1890
4 1 10 78 584 5236 72205
5 3 49 778 18033 971573
6 1 21 584 46661 149636721
7 4 172 18033 19498369
8 1 39 5236 149636721
9 5 573 971573
10 1 68 72205
11 6 1890
12 1 112
13 7
14 1
total 1 3 10 40 228 2380 94495 320863387


Surprisingly, the number of $2$-polymatroids on seven elements is not unimodal in rank. In contrast, matroids are conjectured to be unimodal in rank, and the catalog of matroids with nine elements supports this. By the way, the symmetry in the columns in Table 1 is accounted for by a notion of duality for $2$-polymatroids.

Note that one can obtain the analogue of Table 1 for labeled $2$-polymatroids by computing the automorphism group of each $2$-polymatroid and then using the Orbit-Stabilizer relation. This allowed us to confirm the results of our enumeration through another means. By interpreting a $2$-polymatroid as a solution to a certain integer programming program, the number of labeled $2$-polymatroids can theoretically be computed by integer programming software. Fortunately, the software package SCIP was up to the task when $n \le 7$.

See [Sa14] for more details on all of the above.

Now recall that a matroid $M$ is paving if it contains no circuit of size less than $r(M)$. If both $M$ and $M^{*}$ are paving, then $M$ is sparse-paving. If $M$ is sparse-paving, then one can show that that every set of size less than $r(M)$ is independent and that the dependent $r(M)$-subsets are circuit-hyperplanes; furthermore, the symmetric difference of any two circuit-hyperplanes must be at least $4$. In fact, sparse-paving matroids are characterized by these properties.

It is conjectured that almost all matroids are sparse-paving.

The ideas in the remainder of this post were communicated to me by
Rudi Pendavingh.

We first mention the following background item. Let $S = \{e_1, e_2, \dots, e_n\} \cup \{f_1, f_2, \dots, f_n\}$ be a set of size $2n$. Suppose $(r, S)$ is a matroid. We will pair up the elements of $S$ to define a $2$-polymatroid as follows. Define $S’ = \big\{\{e_1, f_1\}, \{e_2, f_2\}, \dots, \{e_n, f_n\}\big\}$, and define $\rho : S’ \to \mathbb{N}$ by
$$\rho\big(\big\{\{e_{i_1}, f_{i_1}\}, \{e_{i_2}, f_{i_2}\}, \dots, \{e_{i_m}, f_{i_m}\}\big\}\big) = r(\{e_{i_1}, f_{i_1}, e_{i_2}, f_{i_2},\dots, e_{i_m}, f_{i_m}\}).$$
Then $(\rho, S’)$ is a $2$-polymatroid on $n$ elements with $\rho(S’) = r(S)$. Furthermore, every $2$-polymatroid on $n$ elements may be obtained in this manner from a matroid on $2n$ elements. See Section 44.6b of Schrijver’s Combinatorial Optimization or Theorem 11.1.9 of Oxley’s Matroid Theory for details.

Now assume that $r$ is a sparse-paving matroid. If $r(S)$ is odd, then $\rho$ does not detect any of the circuit-hyperplanes of $r$; namely,
\rho(X) =
2|X| & \text{if} \ 2|X| < r(S),\\
r(S) & \text{if} \ 2|X| > r(S).\\
To illustrate, all the rank-$7$ sparse-paving matroids on 14 elements map, in this manner, to a single rank-$7$ $2$-polymatroid on seven elements. However, if $r(S)$ is even, then the circuit-hyperplanes of $r$ are picked up by $\rho$. Perhaps this observation, combined with the conjecture that almost all matroids are sparse-paving, makes the non-unimodality of $2$-polymatroids appear more reasonable.


[MR08] Dillon Mayhew and Gordon F. Royle.
Matroids with nine elements.
J. Combin. Theory Ser. B, 98(2):415–431, 2008.

[Sa14] Thomas J. Savitsky.
Enumeration of 2-polymatroids on up to seven elements.
SIAM J. Discrete Math., 28(4):1641–1650, 2014.

How the infinite matroid got his axioms

In the first post in this series we raised the question of how to find a good notion of infinite matroids with duality. One way to look at the problem is like this: we can’t just define infinite matroids by using the usual axioms for finite matroids and allowing the ground set to be infinite. This fails horribly, because the various standard axiomatisations give rise to quite different notions. We can make them match up again by adding axioms saying that the matroid is finitary (all circuits are finite), but the class of matroids we get in this way isn’t closed under duality.

In this post we’re going to look at a just-so story about how one might solve this problem. We’ll have to wrestle with the axiomatisations until we get natural modifications of all of them which are once more equivalent, but we mustn’t be too violent: we don’t want to lose closure under minors or duality along the way.

A hopeful place to start is with the following Closure Axioms for the closure operator $\text{cl}$ of a finite matroid with ground set $E$:

(CL1) For all subsets $X$ of $E$, $X \subseteq \text{cl}(X)$.
(CL2) For all subsets $X$ of $E$, $\text{cl}(X) = \text{cl}(\text{cl}(X))$.
(CL3) For all subsets $X$ and $Y$ of $E$ with $X \subseteq Y$ we have $\text{cl}(X) \subseteq \text{cl}(Y)$
(CL4) For any $a$ and $b$ in $E$ and any subset $Y$ of $E$ with $a \in \text{cl}(Y \cup {b}) \setminus \text{cl}(Y)$ we have $b \in \text{cl}(Y \cup {a}) \setminus \text{cl}(Y)$.

We can still consider such operators $\text{cl}: {\cal P}E \to {\cal P}E$ even on an infinite set $E$. They are called Idempotent-Exchange operators, or IE-operators for short (the second axiom is idempotence, and the fourth is called the exchange property) [H69]. This is a good place to start because there are very natural definitions of minors and duality for IE-operators.

The dual of $\text{cl}$ is defined as $\text{cl}^*\colon X \mapsto X \cup \{x \in E | x \not \in \text{cl}(E \setminus (X \cup \{x\})\}$. Thus $\text{cl}^*$ has the following property: for any partition of $E$ as $X \dot \cup Y \dot \cup \{x\}$ we have $x \in \text{cl}^*(X) \leftrightarrow x \not \in \text{cl}(Y)$. This property, together with (CL1), characterises $\text{cl}^*$. Thus $\text{cl}^{**} = \text{cl}$. It is isn’t hard to check that if $\text{cl}$ is the closure operator of a matroid then $\text{cl}^*$ is the closure operator of the dual matroid. $\text{cl}^*$ automatically satisfies (CL1) and it satisfies (CL3) if $\text{cl}$ does. Now (CL4) is just a reformulation of the statement we get by applying (CL2) to $\text{cl}^*$. Thus $\text{cl}^*$ satisfies (CL4) because $\text{cl}$ satisfies (CL2) and vice versa. Minors are also easy to define. Thus for example the restriction of $\text{cl}$ to $E’$ is given by $\text{cl}|_{E’} (X) = \text{cl}(X) \cap E’$.

If we try to relate IE-operators to the objects given by the other axiomatisations then we quickly run into problems. We can begin by saying that a set $I$ is $\text{cl}$-independent as long as there is no $x$ in $I$ with $x \in \text{cl}(I \setminus \{x\})$. Then we would like to define bases as maximal independent sets. The trouble is that there might not be any! For example, if $E$ is infinite and we define $\text{cl}(X)$ to be $X$ when $X$ is finite and $E$ when $X$ is infinite then the independent sets are exactly the finite sets, so there are no maximal independent sets.

How can we fix this? One rather silly idea would be to take the collection of IE-operators which have at least one base. Leaving all other problems aside, this collection isn’t minor-closed. Yet more brutally, we could require that $\text{cl}$ and all of its minors each have at least one base. By definition this class is minor-closed. It isn’t hard to see that it is also closed under duality.

This is in fact the right class of infinite matroids. They were discovered by Higgs, who called them B-Matroids [H69]. Oxley showed that B-matroids are a very natural class: he showed that the class of B-Matroids is the largest class of preindependence spaces on which duality and minors are well defined [O92]. (Preindependence spaces are the things satisfying the usual independence axioms for finite matroids.)

The clincher, which not only settles the fact that B-matroids are the right class to work with but also makes it much easier to work with them, is the fact that they have multiple natural axiomatisations [BDKPW13]. At the start of this post, we set out to find those axiomatisations, and we have already found some suitable Closure Axioms (except that we have not yet precisely formulated `all minors have bases’ as an axiom). How could we go about finding the others? It turns out that, as well as slightly tweaking the axiomatisations of finite matroids, we’ll always need a new `all minors have bases’ axiom.

Let’s start by looking at the Independence Axioms for finite matroids:
(I1) The empty set is independent.
(I2) Every subset of an independent set is independent
(I3) If $I$ and $J$ are independent and $J$ has more elements than $I$ then there is $x \in J \setminus I$ such that $I \cup \{x\}$ is still independent.

(I1) and (I2) don’t need to be changed, but the `more elements than’ clause in (I3) becomes less useful when applied to infinite sets. The key idea here is to replace `$J$ has more elements than $I$’ with the far weaker `$J$ is a maximal independent set but $I$ isn’t’ in (I3). Although it looks weaker, we don’t actually lose anything by making this change, because even after the modification (I1), (I2) and (I3) still axiomatise finite matroids.

The requirement that all minors should have at least one base doesn’t follow from (I1), (I2) and our modified (I3). So we need to add it as a new axiom. Formulating this axiom correctly is a subtle matter, because it seems that in order to have a sensible definition of contraction we must first be able to find bases of the sets we wish to contract. The key point is that any minor can be obtained in such a way that the set $I$ of elements that we contract is independent. The independent sets of such contractions are simply sets whose union with $I$ is independent. So we can formulate `all minors have bases’ as follows:

(IM) For any $I \subseteq X \subseteq E$ with $I$ independent, the collection of independent sets $J$ such that $I \subseteq J \subseteq X$ has a maximal element.

To find a base when we contract an arbitrary set $X$ using this axiom, we have to first find a base of $X$ itself. But (IM) allows us to do that too, so this doesn’t cause any problems. (I1)-(I3) together with (IM) really axiomatise B-matroids. The same idea works for bases: the usual base axioms together with (IM) applied to the collection of subsets of bases gives us another axiomatisation. We can also formulate a fifth Closure Axiom (CLM) in the same spirit, saying that the collection of $\text{cl}$-independent sets satisfies (IM). Once more, the collection of operators satisfying (CL1)-(CL4) and (CLM) is exactly the collection of B-matroids.

We won’t discuss the proof that all of these axiomatisations are equivalent (or more precisely cryptomorphic) here, since it is similar to the proof for finite matroids. Instead, we’ll finish by sketching how to get axiomatisations in terms of circuits or the rank function.

In the derivation of other axiomatisations from the circuit axioms, the circuit elimination axiom gets iterated. If one tries to make these proofs work in an infinite context, it turns out that circuit elimination has to be iterated infinitely often, and the proofs fall apart. What is needed is an axiom which allows for controlled iteration of circuit elimination. More precisely, it is enough to require that infinitely many different edges of the same circuit can all be eliminated simultaneously. This principle, the infinite circuit elimination axiom, can be formulated as follows:

(C3) Let $C$ be a circuit, $z$ an edge of $C$ and $X$ a subset of $C \setminus \{z\}$. For each $x \in X$ let $C_x$ be a circuit with $C_x \cap (X \cup \{z\}) = \{x\}$. Then there is a circuit $C’$ with $$z \in C’ \subseteq \left(C \cup \bigcup_{x \in X}C_x\right)\setminus X\,.$$

If we replace the usual circuit elimination axiom with this one and we add an axiom saying that the collection of sets not including any circuit satisfies (IM) then we get an axiomatisation of infinite matroids in terms of their circuits.

The rank function requires the biggest jump from the finite axiomatisation. In order to get a handle on the relationships between sets of infinite rank we must axiomatise not in terms of the rank function but rather in terms of the relative rank function $r$, where $r(A | B)$ is intended to represent the number of elements we need to add to $B$ in order to span $A$. Tweaking the usual rank axioms to corresponding statements about the relative rank function and, as usual, adding an axiom like (IM) gives yet another axiomatisation of infinite matroids.

I hope this has helped to explain why the axioms for infinite matroids look the way they do. Next time we’ll get a better feel for the meaning of these axioms by looking at some examples.

[BDKPW13] H. Bruhn, R. Diestel, M. Kriesell, R. A. Pendavingh and P. Wollan, Axioms for Infinite Matroids. Advances in Mathematics, 239, p18-46
[H69] D. A. Higgs, Matroids and Duality. Colloq. Maths 20 (1969), p215-220
[O92] J. G. Oxley, Infinite Matroids. Matroid Applications (ed. N. White). Encyc. Math. Appl. 40 (CUP 1992), p73-90.

Growth Rates V

Hi everyone, happy new year and sorry for my recent absence/lateness!

Today I am going to say some things about growth rates of minor-closed classes, but in more concrete cases that I’ve been writing about previously. To recap on a definition that has come up many times on this blog, the growth rate function of a minor-closed class of matroids is the definition capturing the answer to a question that Joseph Kung called the ‘primary concern’ of extremal matroid theory: given a minor-closed class $\mathcal{M}$ of matroids, what is the maximum number of elements that a simple rank-$r$ matroid in $\mathcal{M}$ can have? For each nonnegative integer $n$, the growth rate function for $\mathcal{M}$ at $n$ is defined as follows:

$h_{\mathcal{M}}(n) = \max\{|M|: M \in \mathcal{M} \text{ simple}, r(M) \le n\}$.

For instance, for the class $\mathcal{G}$ is the class of graphic matroids we have $h_{\mathcal{G}}(n) = \binom{n+1}{2}$. In fact, the growth rate theorem [GKW09] says that every minor-closed class of matroids with finite growth rate function either has growth rate function in $O(n)$, or contains the graphic matroids (and therefore has growth rate function at least $\binom{n+1}{2}$ for all $n$). Thus, the graphic matroids have the smallest possible growth rate function that is not just linear in $n$.

There are other classes of matroids with growth rate function exactly $\binom{n+1}{2}$ for all $n$, or for all but a few $n$. They necessarily contain the graphic matroids, but can be strictly larger. Several were mentioned in a post by Irene last year; they include the regular matroids, and the class $\mathrm{Ex}(\mathrm{AG}(3,2))$ of binary matroids with no $\mathrm{AG}(3,2)$-minor. The former result was shown by Heller [H57] and the latter by Kung et al [KMPR13]. Given this (and Irene asked a question along these lines in her post), it is natural to ask for a characterisation of exactly which classes of matroids grow like the graphic ones:

Problem 1: Characterise the minor-closed classes of matroids $\mathcal{M}$ that satisfy $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all but finitely many $n$.

or, more concretely, we could ask to characterise the minors whose exclusion gives such a class:

Problem 2: Let $\mathcal{O}$ be a finite set of simple matroids and let $\mathcal{M} = \mathrm{Ex}(\mathcal{O})$ be the class of matroids with no minor in $\mathcal{O}$. Characterise when $\mathcal{M}$ satisfies $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all but finitely many $n$.

Nice Classes

This post will answer both these questions. Before I state the theorem that does this, I’ll give three examples of minor-closed classes that do grow faster than the graphic matroids.

  • The class $\mcevencycle$ of even cycle matroids having a signed graph representation with a blocking pair (that is, a pair of vertices through which all negative cycles pass). This class contains only binary matroids and has growth rate function $\binom{n+2}{3}-3$.
  • The class $\mcsigned$ of signed-graphic matroids having a signed graph representation with a vertex that is contained in every nonloop negative cycle. This class contains matroids representable over every field of odd order, and has growth rate function $\binom{n+2}{2}-2$
  • The class $\mcfree$ that is the union of the class of graphic matroids and the class of truncations of graphic matroids. There is no finite field over which every matroid in this class is representable, and it has growth rate function $\binom{n+2}{2}$.

The superscripts stand for ‘even cycle’, ‘signed graphic’ and ‘truncation’ respectively.  These are three ‘nice’ classes of matroids that are a bit bigger than the graphic matroids, all arising from well-known classes and constructions. The following theorem resolves Problem 1, and will also be enough to resolve 2.

Theorem 1 [GN14]: Let $\mathcal{M}$ be a minor-closed class of matroids with growth rate function in $\Theta(n^2)$. Either

  • $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$, or
  • $\mathcal{M}$ contains one of $\mcevencycle$, $\mcsigned$, or $\mcfree$.

Note that this ‘or’ is really an ‘exclusive or’, since the latter outcome implies that $h_{\mathcal{M}}(n) \ge \binom{n+2}{2}-3$ for all $n \ge 4$ and therefore that the former outcome does not hold. This theorem gives a very nice answer for problem 1; the classes that grow like the graphic matroids are exactly those that do not contain any of three particular classes that are all too big.

To deal with Problem 2, we just need to understand which minors that $\mathcal{O}$ must contain in order that $\mathrm{Ex}(\mathcal{O})$ does not contain any of $\mcevencycle$, $\mcsigned$ or $\mcfree$. This is just saying that $\mathcal{O}$ should contain a matroid from each of these classes. The classes actually intersect, so a single matroid in $\mathcal{O}$ could serve a dual purpose. For $\mathrm{Ex}(\mathcal{O})$ to be quadratically dense, it is also necessary to have some rank-$2$ uniform matroid in $\mathcal{O}$ and no graphic matroid in $\mathcal{O}$. The answer to Problem 2 is therefore in the following corollary:

Corollary 1: If $\mathcal{O}$ is a finite set of simple matroids and $\mathcal{M} = \mathrm{Ex}(\mathcal{O})$, then the following two statements are equivalent:

  1. $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$.
  2. $\mathcal{M}$ contains a rank-$2$ uniform matroid, contains no graphic matroids, and contains a matroid from each of $\mcevencycle$, $\mcsigned$ and $\mcfree$.

This solves the problem in general. We can also obtain specialisations to particular fields. The binary case (that is, where $U_{2,4} \in \mathcal{O}$) says the following:

Corollary 2: If $\mathcal{O}$ is a finite set of simple matroids and $\mathcal{M}$ is the set of binary matroids with no minor in $\mathcal{O}$, then the following two statements are equivalent:

  1. $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$.
  2. $\mathcal{O}$ contains no graphic matroids, and contains a nongraphic matroid in $\mcevencycle$.

When $\mathcal{O} = \{\mathrm{AG}(3,2)\}$ we get (for large $n$) the aforementioned result of Kung et al. There is also a similar corollary for matroids over any fixed odd-order finite field, where $\mcevencycle$ is replaced by $\mcsigned$.

Future Work

Theorem 1 should just be the beginning of an effort to characterise quadratic growth rate functions completely. It would be really nice to answer the following question:

Problem 3: Which functions in $\Theta(n^2)$ can occur as growth rate functions?

It follows from Theorem 1 that any function strictly between $\binom{n+1}{2}$ and $\binom{n+2}{2}-3$ cannot. In general, a conjecture of Geelen, Gerards and Whittle [GGW14] suggests that all such functions are quadratic polynomials with half-integral leading coefficient. Matroid structure theory in [GGW14] should (with enough work) give the answer for classes over any fixed finite field, but I would love to know what can be done without appeals to structure theory, since we are probably a long way off full structure theorems for general matroids.

[H57] I. Heller, On linear systems with integral valued solutions, Pacific J. Math. 7 (1957), 1351-1364.

[GGW14] J. Geelen, B. Gerards and G. Whittle, The highly connected matroids in minor-closed classes, arXiv:1312.5102.

[GKW09] J. Geelen, J. P. S. Kung, and G. Whittle, Growth rates of minor-closed classes of matroids, J. Combin. Theory Ser. B, 99(2):420–427, 2009

[GN14] J. Geelen, P. Nelson, Matroids denser than a clique, arXiv:1409.0777

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