Peter Nelson has been discussing Growth Rates of matroids (in aptly named posts Growth Rates I, II, III and IV). Following his notation, I will denote by $\epsilon(M)$ the number of points of a matroid $M$ (i.e. the number of elements in the simplification of $M$). Deviating just slightly from Peter’s notation, I’ll denote by $h(\mathcal{M},r)$ the growth rate (also called size function) of a class of matroids $\mathcal{M}$. This is the maximum number of points in a matroid in $\mathcal{M}$ of rank at most $r$. In symbols:
$h(\mathcal{M},r)=\textrm{max}\{\epsilon(M)\ |\ M \in \mathcal{M}\ \textrm{and } r(M)\leq r\}$.
In his first post Peter stated the Growth Rate Theorem, a beautiful and very general result on growth rates of minor-closed classes of matroids. For binary matroids, this specialises to saying that, if $\mathcal{M}$ is a minor-closed class of binary matroids, then either:
- $h(\mathcal{M},r)$ is linear, or
- $h(\mathcal{M},r)$ is quadratic, and $\mathcal{M}$ contains all graphic matroids, or
- $\mathcal{M}$ is the class of all binary matroids.
I will discuss results and conjectures about the exact value of the growth rate for specific classes of binary matroids. The conjectures stated here were made possible by Gordon Royle’s database of binary matroids. I’ve been working on some of these conjectures with Joseph Kung, Dillon Mayhew and Gordon Royle. I’ll denote by $EX(M)$ the class of binary matroid with no $M$-minor.
Let’s first look at binary matroids that fall into outcome (1) of the Growth Rate Theorem for binary matroids, i.e. classes of binary matroids that do not contain all graphic matroids. For these classes we know that the growth rate is linear. The first class I’ll consider is that of cographic matroids. A simple cographic matroid arises from a graph where every vertex has degree at least 3. The rank of the matroid (if the graph in question is $G$), is $|E(G)|-|V(G)|+1$. Now suppose that $G$ has a vertex of degree at least 4. Split that vertex into two vertices of degree at least 2 and add an edge between these two vertices (this corresponds to an extension in the matroid). This new graph gives rise to a cographic matroid with the same rank as the initial one, but with one more element. Thus the largest simple cographic matroids arise from cubic (i.e. 3-regular) graphs. With this simple argument we proved that
1) $h(\textrm{cographic matroids}, r)=3(r-1)$.
This was first noted by Joseph Kung in [Ku86].
In the next results I’ll be a bit sloppy and write $EX(G)$ for $EX(M(G))$. I will also be a bit sloppy with small rank cases that can easily be worked out. It is well-known that the class $EX(K_4)$ is exactly the class of series-parallel graphs. Thus:
2) $h(EX(K_4),r)=2r-1$.
Let $W_n$ denote the wheel with $n$ spokes. By giving a decomposition theorem for $EX(W_4)$, Oxley [Ox87] proved that
3) $h(EX(W_4))=3r-2$ if $r$ is odd, and $h(EX(W_4))=3r-3$ if $r$ is even.
The extremal examples are parallel connections of copies of $F_7$ and at most one copy of the rank-4 binary spike (called $Z_4$ in [Ox11]). Having extremal examples of large rank built from small extremal examples seem to be “common” in these types of classes (in fact, that’s also the case for 2) if we see series-parallel graphs as parallel connections of copies of $K_3$). This is also the case for the class $EX(K_{3,3})$, as was shown by Mayhew, Royle and Whittle in [MRW10]. This result follows again from a decomposition theorem for the class $EX(K_{3,3})$.
4) $h(EX(K_{3,3}))=14r/3-a$, where $a=7$ if $r=0$ (mod 3), $a=11/3$ if $r=1$ (mod 3) and $a=19/3$ if $r=2$ (mod 3).
The extremal examples are parallel connections of copies of $PG(1,2)$, $PG(2,2)$ and $PG(3,2)$.
Unfortunately, when looking at the next obvious class what I can state is only a conjecture.
Conjecture 1: $h(EX(K_5),r)=9r/2-a$, where $a=13/2$ if $r$ is odd and $a=6$ if $r$ is even. Moreover, the extremal examples are generalised parallel connections along a line of copies of $C_{12}$ and at most one copy of $F_7$.
The matroid $C_{12}$ is one of the sporadic examples appearing in [MRW10] (where you can also find a definition). While I think that Conjecture 1 may be attacked directly, I wish the best of luck to anyone who would try to prove it via a decomposition theorem for $EX(K_5)$ (which appears to be a much harder problem than the already very difficult decomposition theorem for $EX(K_{3,3}$).
Let’s now move on to classes of binary matroids with quadratic growth rate. A classical result by Heller [He57] gives the growth rate for binary matroids with no $F_7$-minor.
5) $h(EX(F_7),r)=\binom{r+1}{2}$
and it’s not hard to see that the extremal examples are given by graphic matroids. Since $F_7$ is a splitter for the class of binary matroids with no $F_7^*$-minor, we deduce that, for $r\geq 4$,
6) $h(EX(F_7^*),r)=\binom{r+1}{2}$.
In [KDPR13] we showed that the same growth rate is maintained (for $r \geq 5$) by the larger class $EX(AG(3,2))$, and the extremal examples are still graphic matroids.
7) $h(EX(AG(3,2)),r)=\binom{r+1}{2}$.
We also showed that, for rank at least 6, the extremal non-regular example at rank $r$ is the generalised parallel connection along a line of $M(K_r)$ and $F_7$.
What about other classes of binary matroids with quadratic growth? Unfortunately not much is known… However, I do have some interesting conjectures to propose. These are easier to state in terms of even cycle matroids. I mentioned these matroids in my post on biased graphs, but I’ll quickly redefine them here. If $G$ is a graph and $S$ a subset of its edges, we call the pair $(G,S)$ a signed graph. The even cycle matroid arising from $(G,S)$ is the binary matroid represented by the following matrix. Take any binary matrix $A$ representing $M(G)$ (such a matrix has columns indexed by $E(G)$). Now add to $A$ the row incidence vector of $S$ (i.e. a row where entry $e$ is 1 if $e \in S$ and 0 otherwise).
How large can a simple even cycle matroid be? One can see fairly easily that if the even cycle matroid of $(G,S)$ is simple, then $G$ cannot have pairs of parallel edges that are both in $S$ or both not in $S$, and every loop of $G$ has to be in $S$. Moreover we can have at most one such loop. So the largest simple even cycle matroid (for rank $r$) is obtained when we choose $G$ to be $K_r$ with all edges doubled plus a loop, and we choose $S$ to contain exactly one edge per parallel class, plus the loop. The corresponding even cycle matroid is the geometric cone of $M(G)$. So the growth rate for the class of even cycle matroids is $2\binom{r}{2}+1$. The next conjecture states that this is also the growth rate for $EX(PG(3,2))$.
Conjecture 2: For $r \geq 6$, $h(EX(PG(3,2)),r)=2\binom{r}{2}+1$, and the extremal examples for $r\geq 7$ are even cycle matroids.
A binary matroid $M$ is an even cycle matroid if and only if it has a binary single element extension $M’$ (by an element $e$) such that $M’/e$ is graphic. Since any single element contraction of $PG(3,2)$ is not graphic, $PG(3,2)$ is not an even cycle matroid and the whole class of even cycle matroids is contained in $EX(PG(3,2))$.
Let $PG(3,2)^-$ denote the matroid obtained from $PG(3,2)$ by deleting an element. Then $PG(3,2)^-$ is also not an even cycle matroid. The next conjecture is weaker (and possibly easier to prove) than Conjecture 2.
Conjecture 3: For $r \geq 6$, $h(EX(PG(3,2)^-),r)=2\binom{r}{2}+1$, and the extremal examples for $r\geq 7$ are even cycle matroids.
What if we delete two elements from $PG(3,2)$? (I’ll call the corresponding matroid $PG(3,2)^{- -}$). I conclude the post with this conjecture.
Conjecture 4: For $r \geq 6$, $h(EX(PG(3,2)^{- -}),r)=\binom{r}{2}+2r-2$.
The extremal examples are again even cycle matroids, but not the same as for Conjecture 2. This is because $PG(3,2)^{- -}$ is an even cycle matroid itself, so $EX(PG(3,2)^{- -})$ cannot contain the whole class of even cycle matroids. The (conjectured) extremal examples in this class arise from signed graphs $(G_r,S_r)$ described as follows. Pick two vertices $u$ and $v$ in $K_r$. Double all the edges incident with $u$ or $v$ (or both) and add a loop. Call the resulting graph $G_r$. Now put in $S_r$ exactly one edge per parallel class of size 2, plus the loop (and no other edges). It can be shown by induction on $r$ (if you know the signed graph representation of $PG(3,2)^{- -}$) that these even cycle matroids do not, indeed, contain $PG(3,2)^{- -}$ as a minor.
References
[Ox87] J. Oxley, The binary matroids with no 4-wheel minor, Trans. Amer. Math. Soc. 301, 1 (1987), 63-75.
[Ox11] J. Oxley, Matroid theory, second ed., vol. 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, 2011.
Nice post, Irene! I think I believe all those conjectures.
There are a few things about the kind of growth rate results you consider, although unfortunately none of your conjectures, that are implied by a result from Rohan Kapadia’s thesis, http://www.math.uwaterloo.ca/~rfkapadi/thesis.pdf . His (and Jim’s) Theorem 4.0.2 states, for all n, that a vertically 5-connected binary matroid with a large clique minor is either graphic, or has a minor that is a simple, co-simple extension of a rank-n clique.
There is a connectivity reduction to be done, but after that, Rohan and Jim’s result implies that if some minor-closed class of binary matroids has growth rate function exceeding $\binom{r+1}{2}$ for infinitely many $r$, then the class contains arbitrarily large matroids that are simple cosimple extensions of a clique.
This implies (by just looking at the binary matrices corresponding to such an extension and contracting the ‘non-graphic’ element) that any such class contains one of two subclasses. The first is the even-cycle one that you describe in your post, that has growth rate function $\binom{r}{2} + 2r – 2 = \binom{r+2}{2}-3$, and the second is the one you get by appending an all-ones column to the representation of a clique that contains an identity matrix, and then contracting the new column. This is a class with growth rate function $\binom{r+2}{2}$. The following theorem results:
If $\mathcal{M}$ is a minor-closed class of binary matroids with $h_{\mathcal{M}}(r) > \binom{r+1}{2}$ for infinitely many $r$, then $\mathcal{M}$ contains one of the two subclasses discussed above, and $h_{\mathcal{M}}(r) \ge \binom{r+2}{2}-3$ for all $r \ge 3$.
So there is a ‘gap’ between $\binom{r+1}{2}$ and $\binom{r+2}{2}-3$ that no binary growth rate function can fill. By looking at the minors that these two special classes contain, you can also prove (I think) that $F_7$, $F_7^*$ and AG$(3,2)$ are the only simple minors whose exclusion gives growth rate $\binom{r+1}{2}$ for large $r$.
Hi Peter! Thanks for your comments. I didn’t know about that theorem of Rohan and Jim. I’m quite intrigued by the question of which growth rates can occur for binary matroids.
About your last “conjecture”: I think there are other simple matroids aside from $F_7$, $F_7^*$ and $AG(3,2)$ that give growth rate $\binom{r+1}{2}$, like the rank-4 spike $Z_4$.
Oh, you’re right about that spike, yeah. I’ll revise my statement now and claim that’s the only other one. Even if that’s wrong, it takes a small finite check to see what the right list is – it is just the nongraphic matroids common to both those special classes I mentioned (since excluding the minor better kill both those classes for the growth rate to be at most $\binom{r+1}{2}$ and the minor better not be graphic, as otherwise the class is linearly dense). Do the techniques in your paper work for $Z_4$? It seems like there shouldn’t be that many obstacles.
Hi Peter,
Consider the 12-element rank-4 binary matroid $N$ obtained from a representation of $M(K_5)$ with an identity submatrix by adding a column with three ones and a column with four ones.
I believe that excluding this should give growth rate $\binom{n+1}{2}$ since it is a minor of every 1-element extension of $M(K_6)$ (there are only two nonisomorphic extensions of $M(K_6)$, one has a $PG(3, 2)$-minor and the other becomes $N$ when you contract the new point).
All the matroids you listed, $AG(3, 2)$, $F_7$, $F_7^*$, and the spike are restrictions of this.
Also, if you want to know which functions can occur as binary growth rate functions, the answer is implicit in Theorem 4.2 of this paper: http://arxiv.org/abs/1312.5012
It’s not the easiest result to digest, but it should imply (again, I haven’t thought about this rigorously) that if $f$ is a quadratic growth rate function for a minor-closed class of binary matroids, then there exist $k \in \mathbb{Z}^+$, $d \in \mathbb{Z}_0^+$ such that $f(n) = \binom{n+k}{2} – d$ for all sufficiently large $n$. $d$ will also be bounded above by some sensible function of $k$.
It’s very nice to see that there is renewed interest in the growth rates of minor-closed classes of binary and other matroids. Perhaps those interested can get together and have an informal discussion at the matroid workshop at Princeton. Please contact me if you are interested.
I agree with Peter that the paper GGW, “The highly connected matroids in minor-closed classes” has, more or less, determined what all the possible growth rates of binary matroids [and theoretically all GF(q)-matroids] are. What remain, it seems, are “exact” questions: what happens if you exclude a specific binary matroid?
Although the asymptotic behaviour is known, there are technical issues if one wishes to prove anything, not least the “finite barrier”: there is usually a lot of finite junk at low rank and one needs much computer power to break through this. As an example, it’s almost certain that excluding the rank-4 spike [or AG(3,2) + a point]
gives size function $\binom {r+1}{2}$ but getting a proof would require a large computer search.
I might mention that there are interesting questions/conjectures in ternary and other matroids. My favorite one is: what is the size function if we exclude $AG(2,3)$ [this is the ternary affine plane] from ternary matroids. The conjectured answer is $r^2.$
when $r$ is sufficiently large, and maybe $r \geq 4$ would work.