So far in this series we have focused on the search for a good way to axiomatise infinite matroids. Now that we have the axioms, our next aim is to get a better sense of what sort of ground they stake out by taking a whirlwind tour of the known examples of infinite matroids.

Let’s start off with some very familiar examples: The set of subsets of a given set which have size at most $n$,  the set of (edge sets of) forests in a given graph and the set of linearly independent subsets of a given family of vectors in a vector space each give the set of independent sets of a matroid. This is true even if we allow the set, graph or family of vectors in question to be infinite. Of course, all of these examples are finitary (that is, a set is independent as soon as all of its finite subsets are). We saw earlier that it would be a bad idea to only consider finitary matroids, because we would lose the power of duality. But we certainly want our notion of infinite matroid to include all of these examples. Since we now have a concept of infinite matroid which is closed under duality, we get all their duals for free, too.

What about matroids which are neither finitary nor cofinitary? At first it looks like a simple way to construct such examples would be by building infinite uniform matroids. But the usual definition of uniformity, namely that the bases should be all sets of a given size, becomes silly when we replace `size’ by `cardinality’, since infinite sets can have proper subsets of the same cardinality. It doesn’t help to define things in terms of independent sets. For example, we might hope to have a matroid whose independent sets are just the countable subsets of some uncountable set $E$. But since there are no maximal countable sets, this object wouldn’t even have any bases.

The right notion of uniformity for infinite matroids is as follows: if $B$ is a base and $x$ and $y$ are elements of the ground set $E$ with $x$ in $B$ but $y$ not in $B$ then $B – x + y$ is also a base. It isn’t hard to check that this is equivalent to uniformity when applied to finite matroids. Now we might try to build infinite uniform matroids by just recursively choosing the set of bases, paying attention to the fact that (because of the definition above) whenever we choose a set $B$ we also have to choose all sets $B’$ for which $B \setminus B’$ and $B’ \setminus B$ are finite and of equal size. This simpleminded strategy works, given some weak assumptions [BG15]. Because this recursive construction gives us so much freedom, infinite uniform matroids are much more varied than finite ones.

The flexibility of this construction lets us resolve a very basic question: must it be true that any two bases of an infinite matroid have the same cardinality? Higgs showed that this is true if we assume the continuum hypothesis [H69a]. But using the freedom mentioned above we can also show that it is consistent that the following naive plan for building a matroid with bases of different sizes actually works: run the above recursive construction to build a uniform matroid on an uncountable set, and begin by nominating some countable subset and some uncountable subset as bases [BG15]. So the answer to the question above is actually independent of the usual axioms of set theory.

The other examples we’ll look at today will all be associated to graphs. The finitary matroid mentioned above, whose circuits are (edge sets of) cycles in a given graph $G$, is called the finite-cycle matroid of $G$. There is another finitary matroid whose circuits are the finite bonds of $G$. But these two are no longer dual to each other. The circuits of the dual of the finite-bond matroid correspond to topological circles in a topological space, called the end-compactification of $G$. This space is obtained from $G$ by adding some points at infinity, called ends. These `topological cycles’ were actually first invented for a very different reason and helped to motivate the current axiomatisations of infinite matroids. This was the starting point of our story.

So although there is one canonical matroid associated to a finite graph, for an infinite graph we already have two. In fact there are many more. For example, Higgs showed that there very often is a matroid whose circuits are the (edge sets of) finite cycles or double rays in the graph $G$. This doesn’t always work. For example, in the Bean Graph, shown below, the set of bold edges and the set of dashed edges are both bases but there is no way to replace the edge $e$ with a bold edge in the dashed basis and still have a base. So the base axioms don’t hold.

This is essentially all that can go wrong: Higgs showed [H69b] that if $G$ includes no subdivision of the Bean Graph then there is a matroid, called the algebraic-cycle matroid of $G$, whose circuits are given as above by the finite cycles and double rays.

Another fertile way to build more matroids from graphs is to ignore some of the ends. More precisely, we consider topological circles in a space obtained from the end-compactification of $G$ by deleting some of the ends. For example, the double ladder has two ends and we might wish to keep only one of them, giving rise to the following space:

Once more it is true that the (edge sets of) topological circles give the circuits of a matroid, as long as the set of ends we remove is Borel [BC15].

Is there any unifying theme to this profusion of examples, except that they can all be built somehow from graphs? Yes! Each of these matroids can represented by a topological space. The finite-cycle matroid of $G$ is represented by the geometric realisation of $G$ and the topological-cycle matroid by the end-compactification. The rich collection of matroids we just discussed are represented by subspaces of the end-compactification. The algebraic-cycle matroid is represented by the space obtained from the end-compactification by identifying all the ends.

More generally, there is a precisely specified class of graph-like topological spaces and a  notion of representation of a matroid by such a space, such that a matroid is representable in this way if and only if, firstly, every intersection of a circuit with a cocircuit is finite (this corresponds to the fact that topological circles are compact), and secondly, it satisfies the usual excluded-minor characterisation of graphic matroids.

Thus the wide range of ways of building infinite matroids from graphs corresponds to the variety of ways of building such graph-like spaces out of graphs. We have seen that this construction doesn’t always give a matroid, as with the Bean Graph above, but it does so often enough to give a rich variety of matroids. For example, we always get a matroid when the space is compact. Hence the (edge sets of) topological circles in the following picture give the circuits of a matroid, the Sierpinski Matroid:

Before we conclude, lets just glance at a couple of the other kinds of infinite matroid which have been discovered. There are frame matroids: Matthews and Oxley showed that in any graph $G$ the edge sets of subdivisions of the following graphs gives the set of circuits of a matroid [MO77], and a more general construction works in in infinite biased graphs.

There are infinite gammoids, defined either in terms of bipartite graphs or of directed graphs. The question of when these constructions give rise to matroids is a delicate one and has been investigated by Afzali, Law and Müller [ALM15].

Finally, we can define the truncation of a non-free matroid $M$ to have as independent sets the proper subsets of independent sets of $M$, and all truncations and co-truncations of infinite matroids are again infinite matroids. This gives lots of new examples, such as the matroids whose circuits are edge sets of topological copies of the following spaces in a graph-like space:

This is not so much a class of examples as a way to build new infinite matroids from old. We’ll consider some other fertile ways to combine infinite matroids next time.

[ALM15] H. Afzali, Hiu-Fai Law and M. Müller, Infinite gammoids. Electronic J. Comb. 22 (2015), #P1.53
[BC15] N. Bowler and J. Carmesin, Infinite Matroids and Determinacy of Games, submitted to LMS, available here.
[BG15] N. Bowler and S. Geschke,  Self-Dual Uniform Matroids on Infinite Sets, to appear in the Bulletin of the American Mathematical Society, available here.
[H69a] D. Higgs, Equicardinality of bases in B-matroids, Canadian Math. Bul. 12 (1969), 861–862.
[H69b] D. Higgs. Infinite graphs and matroids. Recent Progress in Combinatorics, Proceedings Third Waterloo Conference on Combinatorics, Academic Press (1969),  245-53.
[MO77] L. Matthews, J. Oxley, Infinite graphs and bicircular matroids. Discrete Mathematics, Volume 19, Issue 1 (1977), 61-65.

$\newcommand{\PG}{\text{PG}}$

Denser than a Geometry

Hello everyone. In my last post, I discussed an unavoidable minor theorem for large matroids of density greater than $\binom{n+1}{2}$, which as a consequence characterised exactly the minor-closed classes of matroids that grow like the the graphic matroids. Today I’ll write about the exponential analogue of this problem; this appears in a paper of mine [2] available on the arXiv, and I will also be speaking on this topic at the matroid session of the upcoming CanaDAM conference in Saskatchewan.

I’ll first state a nice theorem of Kung, specialized to prime powers:

Theorem: If $q$ is a prime power, and $M$ is a simple rank-$n$ matroid with $|M| > \frac{q^n-1}{q-1}$, then $M$ has a $U_{2,q+2}$-minor.

This is certainly an important theorem – it says that if $M$ has too many elements to be a projective geometry over GF$(q)$, then $M$ has a rank-$2$ minor with the same property. However, if $n$ is large then this is somewhat unsatisfying, as the $U_{2,q+2}$-minor has constant size, and does not really ‘explain’ why $M$ is so dense. We would like a similar theorem that, instead of finding a $U_{2,q+2}$-minor, finds an unavoidable minor whose size grows with $n$.

What should such a minor be? That is, what are the large matroids that are ‘canonically’ denser than a projective geometry over GF$(q)$?

The first example is easy; rank-$2$ matroids can contain arbitrarily many elements, so the uniform matroid $U_{2,t}$ for some large $t$ must appear as an outcome. The direct sum of $U_{2,q^n}$ and $U_{n-2,n-2}$, for example, is a rank-$n$ matroid with more elements than $\PG(n-1,q)$, and essentially no more interesting structure.

Another matroid denser than $\PG(n-1,q)$ is simply a projective geometry $\PG(t-1,q’)$ over finite field GF$(q’)$.with $q’ > q$. This is our second outcome.

The next two outcomes are more interesting. An obvious way to construct a matroid denser than $\PG(n-1,q)$ is to perform a single-element extension. By modularity, every extension of $\PG(n-1,q)$ consists of adding a point freely to some flat $F$. The smallest simple case is where $F$ is a line: we write $\PG^{\mathrm{line}}(n-1,q)$ for the matroid formed by adding a point freely to a line of $\PG(n-1,q)$. The ‘largest’ case is when $F$ is the entire ground set, so the extension is free. We write $\PG^{\mathrm{free}}(n-1,q)$ for this matroid. The matroids $\PG^{\mathrm{line}}(m-1,q)$ and $\PG^{\mathrm{free}}(n-1,q)$ coincide for $n = m = 2$, but are not minors of eachother for any $m,n \ge 3$; they will thus occur as separate outcomes in our theorem. On the other hand, it is not hard to show that any simple extension of $\PG(2n-1,q)$ has one of $\PG^{\mathrm{line}}(n-1,q)$ or $\PG^{\mathrm{free}}(n-1,q)$ as a minor; thus, no further single-element extensions are needed as outcomes. Here is the theorem.

Theorem 1 [2]: For every prime power $q$ and all $t \ge 3$, there exists $n \in \mathbb{Z}$ so that, if $M$ is a simple matroid with rank at least $n$ and $|M| > \frac{q^{r(M)}-1}{q-1}$, then $M$ has a minor isomorphic to one of the following:

•  $U_{2,t}$,
• $\PG(t-1,q’)$ for some $q’ > q$,
• $\PG^{\mathrm{free}}(t-1,q)$, or
• $\PG^{\mathrm{line}}(t-1,q)$.

Like in the quadratic case, we can apply this theorem to identify minor-closed classes that grow no faster than the GF$(q)$-representable matroids. For instance, if $q’$ is the next prime power after $q$, and $\ell$ is an integer so that $q \le \ell < q’$, then, for $t = \ell+2$, all four of the above minors can be shown to contain a $U_{2,\ell}$-minor. We thus have the following:

Corollary 1: Let $q$ and $q’$ be consecutive prime powers and $\ell$ be an integer so that $q \le \ell < q’$. If $M$ is a simple matroid with sufficiently large rank and no $U_{2, \ell+2}$-minor, then $|M| \le \frac{q^{r(M)}-1}{q-1}$.

Spikes and Swirls

Let $X = \{x_1,\dotsc,x_t\}$ and $Y = \{y_1, \dotsc, y_t\}$ be disjoint $t$-element sets. A rank-$t$ free spike is the matroid $\Lambda_t$ with ground set $X \cup Y$ whose non-spanning circuits are exactly the four-element sets of the form $\{x_i,x_j,y_i,y_j\}$ for $i  \ne j$. The rank-$t$ free swirl is the matroid $\Delta_t$ with ground set $X \cup Y$ whose non-spanning circuits are exactly the four-element sets $\{x_i,x_{i+1},y_i,y_{i+1}\}$, where addition is modulo $t$.  Both free spikes and free swirls arise as pathologies in matroid representation theory.

Let $q \ge 3$ be a prime power and let $t \ge 3$. One can show (see [1]) that

• $\Lambda_t$ is GF$(q)$-representable if and only if $q$ is non-prime or $t \le q-2$.
• $\Delta_t$ is GF$(q)$-representable if and only if $q-1$ is non-prime or $t \le q-3$.

Using this, one can hunt for free spikes and swirls in the list of unavoidable minors in Theorem 1. There is a bit of case analysis to see what theorems fall out, but we get a few different corollaries that give upper bounds on the densities of matroids with out line-, spike-, and/or swirl-minors. All of the upper bounds in these corollaries are the densities of projective geometries, and are best-possible because the geometries themselves are tight examples.

Corollary 2: Let $\ell \ge 2$ and $t \ge 3$ be integers. If $M$ is a matroid of sufficiently large rank with no $U_{2,\ell+2}$-minor and no $\Lambda_t$-minor, then $|M| \le \frac{p^{r(M)}-1}{p-1}$.

Corollary 3: Let $\ell \ge 3$ and $t \ge 3$ be integers. If $M$ is a matroid of sufficiently large rank with no $U_{2,\ell+2}$-minor, no $\Lambda_t$-minor and no $\Delta_t$-minor, then $|M| \le \tfrac{1}{2}(3^{r(M)}-1)$.

The next corollary mostly tells you how dense a matroid can be if you exclude a line and a free swirl has a minor. However, it weirdly fails to apply to some $\ell$ because of the oddness of representation of free swirls. The only fields that can’t represent free swirls are are the ones of order $2^p$, where $2^p-1$ is prime. A prime of the form $2^p-1$ for another prime $p$, like $2^3 – 1 = 7, 2^5 – 1 = 31$ or $2^7 – 1 = 127$, is a Mersenne prime; it is not even known if there are infinitely many.

Corollary 4: Let $2^p-1$ and $2^{p’}-1$ be consecutive Mersenne primes, and let $k$ and $\ell$ be integers so that $2^p \le \ell < \min(2^{2p} + 2^p, 2^{p’})$ and $k \ge \max(3,2^p-2)$. If $M$ is a simple matroid of sufficiently large rank with no $U_{2,\ell+2}$ or $\Delta_k$-minor, then $|M| \le \frac{2^{pr(M)}-1}{2^p-1}$.

This fails to apply to some $\ell$, but only if $\ell$ is (roughly) greater than the square of a Mersenne prime but smaller than the next Mersenne primes. The first pair of Mersenne primes this far apart are $2^{127}-1$ and $2^{521}-1$, so for some $\ell$ around this size, the above corollary says nothing. The actual fact of the matter depends on the very poorly understood distribution of the Mersenne primes, so I don’t expect much improvement there in the near future.

Thanks, and see you next time!

[1] J Geelen, J.G. Oxley, D. Vertigan, G. Whittle, Totally free expansions of matroids, J. Combin. Theory. Ser. B 84 (2002), 130-179.

[2] P. Nelson,  Matroids denser than a projective geometry, to appear, SIAM Journal on Discrete Mathematics.

There will be a Summer School in Infinite Matroid Theory from the 19th to 25th of July at the youth hostel in Bosau, near Hamburg, Germany. More details are available at http://www.math.uni-hamburg.de/home/bowler/im15

It is aimed at doctoral students and other young researchers, especially graph theorists, who are already familiar with the basic theory of finite matroids. The aim is to give the participants a sufficient grounding in the theory of infinite matroids that they can start to work independently in the field. The organisers are Nathan Bowler and Johannes Carmesin.

There are no accommodation costs, and we have a little money to help pay for travel in exceptional cases. If you have any questions, feel free to email us at im15@math.uni-hamburg.de

Guest post by Sandra Kingan

Growth rates are a popular topic on Matroid Union. Peter Nelson has written five posts on it: Growth Rates I, II, III, IV, V.  Irene Pivotto has also written a post on it.

Following James Oxley’s book [Oxley, 2012] , the growth rate function of a minor-closed class $\mathcal M$, denoted by $h_{\mathcal M}(r)$, is defined as the maximum number of elements in a simple rank-$r$ matroid in $\mathcal M$ if the number is finite and infinity otherwise (p. 570). A simple matroid is extremal in a minor-closed class $\mu$ of matroid if $M\in \mu$, but $\mu$ contains no simple single-element extension of $M$ that has the same rank as $M$ (p. 572).

For example, if $\mathcal M$ is the class of graphs, then the complete graph of rank-$r$ denoted by $K_{r+1}$, for $r\ge 1$ is the rank-$r$ extremal matroid. The growth rate function is the size of $K_{r+1}$ which is $\frac {r(r+1)}{2}$.  On the other hand if $\mathcal M$ is the subclass of planar graphs, then we don’t know precisely the extremal planar graphs, but we do know the growth rate function. A straightforward graph theoretic argument (found in any graph theory textbook) shows that the number of edges of a “maximal” planar graph is $3r-3$. (In graph theory a maximal planar graph is defined as one to which if you add one more edge it becomes non-planar.)

Similarly, if $\mathcal M$ is the class of binary matroids, then the rank-$r$ projective geometry $PG(r-1, 2)$, for $r\ge 2$, is the rank-$r$ extremal matroid. The growth rate function is the size of $PG(r-1, 2)$ which is $2^r-1$.

Within the class of binary matroids lies the class of cographic matroids (matroids whose duals are graphic). Again we don’t know precisely the extremal cographic matroids, but we can prove that the growth rate function is $3r-3$ (as shown by Joseph Kung and further explained further in Pivotto’s post). Also in her post is the growth rate of series-parallel networks. Series-parallel networks are formed by starting with a single edge or loop and repeatedly adding edges in parallel or edges in series (turning one edge into two edges by putting a vertex on the edge). The growth rate of series parallel networks is $2r+1$. See [Oxley Section 5.4] and [Oxley 1987, Section 3] for the explanation.

The first extremal result is generally attributed to Paul Turán. The class he considered was the class of graphs with no $K_{s+1}$-subgraph. (Mantel proved the $K_3$ case earlier.) Turán proved that the rank $r$ extremal graph is a specific type of complete s-partite graph (see Wikipedia). The growth rate function is $\frac{(s-1)(r+1)^2}{2s}$ [Turan, 1941].

With respect to the growth rate function we are keen on knowing if it is linear or a higher order polynomial like quadratic or exponential. See Nelson’s posts for detailed explanations on this.

In 1963 G. A. Dirac determined the graphs without two vertex disjoint cycles [Dirac, 1963]. Excluding two vertex-disjoint cycles in a 3-connected graph is equivalent to excluding the prism graph $(K_5\backslash e)^*$ as a minor. So essentially Dirac determined the 3-connected graphs with no prism minor. He found that the 3-connected members of this class are $K_5$, $K_5 \backslash e$, the infinite family of wheel graphs $W_r$, for $r\ge 4$, and $K_{3,p}$, $K’_{3,p} $, $K”_{3,p} $ or $K”’_{3,p}$, for some $p\ge 3$.

Theorem 1.  A simple $3$-connected graph has no minor isomorphic to $(K_5\backslash e)^*$ if and only if it is isomorphic to $W_r$ for some $r\ge 3$, $K_5$, $K_5 \backslash e$, $K_{3,p}$, $K’_{3,p} $, $K”_{3,p} $ or $K”’_{3,p}$, for some $p\ge 3$.

Observe that there are two very distinct 3-connected infinite families here: $W_r$ and $K_{3, p}”’$. The size of $W_r$ is $2r+1$ for $r\ge 3$ and the size of $K_{3, r-2}”’$ is $3r-3$ for $r\ge 5$. Both of these 3-connected infinite families are growing linearly. I’ve heard the word “monarchs” used to describe $W_r$ and $K_{3, p}”’$; I think Jack Edmonds used this term. Monarchs is a good word to describe them.

Matroids that are not 3-connected may be pieced together from 3-connected matroids using direct-sums and 2-sums [Oxley, 2012, 8.3.1]. This result was first proven by Bixby in 1972. This is a terrific decomposition result that allows us to focus on just the 3-connected matroids in the family. Thus if we know the 3-connected matroids we can build the 2-connected ones via the operation of two sums.

Now extremal matroid is defined as the simple rank-$r$ matroid of maximum size. So 2-sums and even direct sums are allowed. But when the class contains $W_r$ and $K_{3, r-2}”’$ with $W_r$ growing at rate $2r$ and $K_{3, r-2}”’$ growing at rate $3r-3$, the latter dominates any rank-$r$ graph that can be constructed from direct sum or 2-sum. The proof is straightforward case-checking. Thus the growth rate of the class of graphs with no prism minor is $3r-3$ and the rank-$r$ extremal matroid is $K_{3, r-2}”’$. Even if we were not able to say precisely what the growth rate is, once the 3-connected families are found, and found to be growing linearly, piecing together using direct sum and 2-sum will still give a linear growth rate.

Moving on let’s take a look at Oxley’s 1987 result where he determined the 3-connected matroids with no 4-wheel minor [Oxley, 1987]. The main theorem of that paper is Theorem 2.1 and the key component of the main theorem is Theorem 2.2 which is stated below. Let $Z_r$ denote the $(2r+1)$-element rank-$r$ binary spikes. They are non-regular matroids represented by the binary matrix $[I_r| D]$ where $D$ has $r+1$ columns labeled $b_1, \dots b_r, c_r$. The first $r$ columns in $D$ have zeros along the diagonal and ones elsewhere. The last column is all ones.

Theorem 2. A 3-connected binary non-regular matroid has no minor isomorphic to $P_9$ or ${P_9}^*$ if and only if it is isomorphic to $F_7$, ${F_7}^*$, $Z_r$, ${Z_r}^*$, $Z_r \backslash b_r$, or $Z_r \backslash b_r$, for some $\ge 4$.

Observe that the 3-connected infinite family $Z_r$ is growing at the rate of $2r+1$ elements. In Section 3 of his paper Oxley states without proof (details are straightforward) that the growth rate of the class of binary matroids with no 4-wheel minor is $3r-2$ if $r$ is odd and $3r-3$ if $r$ is even (Theorem 3.1). Why the difference: $2r+1$ versus $3r-2$? The answer is given in the second part of the statement of the theorem, you can 2-sum $F_7$ with itself or $F_7$ with $Z_4$ or $F_7$ with $U_{2,3}$ and get slightly larger rank-$r$ matroids as compared to $Z_r$.

This is why it is sufficient to know the 3-connected members of a class, and for all practical purposes the definition of extremal matroid really should have had 3-connected in it. The definition of extremal matroid made in the 1950s did not forsee Bixby’s result. There’s probably no point changing any definition, but it must be understood clearly that if the 3-connected members of a class are known, then so is the growth rate.

This raises the question: What if we don’t know the 3-connected members, but we have a decomposition result? The first and most well-known such result in Matroid Theory is Paul Seymour’s regular matroid decomposition. He proved that if $M$ is a 3-connected matroid in $EX(F_7, F_7^*)$, then $M$ can be constructed by piecing together graphic and cographic matroids and $R_{10}$, which is a special 10-element matroid [Seymour, 1980].  The  3-connected regular matroids are not known precisely. However, in 1957 Heller showed that the growth rate of the class of regular matroids is $\frac {r(r+1)}{2}$. His proof predates Seymour’s decomposition theorem. I have not seen a proof of growth rate of regular matroids based on the Seymour’s decomposition theorem. Perhaps if someone has, a reference could be mentioned in the comments.

More recently, Kung, Mayhew, Pivotto, and Royle showed the growth rate of $EX(AG(3,2)$ is $\frac {r(r+1)}{2}$. See Nelson’s fifth post on growth-rates. In that post he said:

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:

In a paper titled “Growth rates of binary matroids with no $P_9^*$-minor,” I found another class that exhibits this behavior.

Theorem 3. Let $M$ be a simple rank-$r$ binary matroid with no $P_9^*$ minor. Then, $|E(M)| \le \frac {r(r+1)}{2}$ with this bound being attained if and only if $M\cong K_{r+1}$. Moreover, the growth rate function of non-regular matroids in $EX[P_9^*]$ is $4r-5$, for $r\ge 6$.

The technique in Oxley’s 1987 paper is Seymour’s Splitter Theorem which was used to obtain the precise 3-connected members. The technique in my paper is the Strong Splitter Theorem, which was joint work with Manoel Lemos, where we built on the Splitter Theorem. Using it I was able to find the 3-connected members for $EX({P_9}^*)$. This approach is completely different from the approach Kung, Mayhew, Pivotto, and Royle adopted to find $EX(AG(3,2)$.

This post is getting quite long. In my next post I will describe the complete structure of the class $EX(P_9^*)$ and explain how I can say precisely the growth rate of the 3-connected non-regular matroids is $4r-5$. Note that $4r-5$ is the growth rate of the rank-$r$ 3-connected family, but it is large enough that it dominates any rank-$r$ 2-connected matroid pieced together from small 3-connected matroids.

The next post will appear on my blog Graphs, Matroids, etc.

References:

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

[Kingan, 2015] S. R. Kingan, Growth rates of binary matroids with no $P_9^*$-minor,  arXiv:1412.8169.

[Kingan and Lemos, 2014] S. R. Kingan and M. Lemos (2014), Strong Splitter Theorem , Annals of Combinatorics, Vol. 18 – 1, 111 – 116.

[Kung, Mayhew, Pivotto, Royle, 2013] J. Kung, D. Mayhew, I. Pivotto, and G. Royle, Maximum size binary matroids with no AG(3,2)-minor are graphic,  http://epubs.siam.org/doi/abs/10.1137/130918915

[Oxley, 1987] J. G. Oxley (1987). The binary matroids with no 4-wheel minor, {\it Trans. Amer. Math. Soc.} {\bf 154}, 63-75.

[Oxley, 2012] J. G. Oxley (2012). {\it Matroid Theory}, Second Edition, Oxford University Press, New York.

[Seymour, 1980] P. D. Seymour (1980) Decomposition of regular matroids, {\it J. Combin. Theory Ser. B} {\bf 28}, (1980) 305-359.

[Turán, 1941] P. Turán (1941), “On an extremal problem in graph theory”, Matematikaiés Fizikai Lapok (in Hungarian) 48: 436–452.