This post is a spiritual successor to Rutger’s post from a few months ago. In that post, Rutger discussed the rank3 excluded minors for GF(5)representability. Here I’m going to discuss the 10element excluded minors for GF(5)representability.
Recall that the excluded minors for GF(5)representability on at most 9 elements are known, thanks to Dillon Mayhew and Gordon Royle’s work enumerating all matroids on at most 9 elements [MR2008]. The strategy discussed here, to find the 10element excluded minors, is due to Rudi Pendavingh and Stefan van Zwam [PvZ2010]: it uses the Hydra partial field hierarchy. For those unfamiliar with partial fields, Stefan previously posted about them, in detail, see part 1, part 2, and part 3. For the purposes of this post, it is probably sufficient to observe that representability over a partial field can be used to capture something “more general” than representability over a field: for example, representability over a set of fields, or, of particular relevance here, having at least some particular number of inequivalent representations over a field. Rudi and Stefan [PvZ2010] defined the Hydra$i$ partial field, for each $i \in \{1,2,3,4,5,6\}$, which can be used to capture matroids with at least $i$ inequivalent representations over GF(5). For simplicity, assume we only care about 3connected matroids having a $U_{2,5}$ or $U_{3,5}$minor. Then a matroid is representable over the Hydra$i$ partial field if and only if it has at least $i$ inequivalent representations over GF(5). Note that Hydra1 is just GF(5), and it is known that a matroid has at most 6 inequivalent representations over GF(5) [OVW1996]. Moreover, Rudi and Stefan showed that the class of Hydra5 and Hydra6representable matroids coincide: that is, if a matroid has at least five inequivalent representations over GF(5), then it in fact has precisely six [PvZ2010]. So there are really five layers to the Hydra partial field hierarchy.
Suppose we know all the excluded minors for Hydra5representability and want to find the excluded minors for Hydra4representability. Consider a matroid that has exactly four inequivalent representations over GF(5): it is Hydra4representable but not Hydra5representable, so it contains an excluded minor for Hydra5representability as a minor. This tells us that once we understand the Hydra5representable matroids, we can restrict our attention to matroids that have an $N$minor, where $N$ is an excluded minor for Hydra5representability that is Hydra4representable. In theory, we could attempt to repeat this process at each layer, starting with Hydra5, then Hydra4, all the way to Hydra1, that is, GF(5). Of course, finding all the excluded minors for Hydra5 is a very difficult problem, let alone any of the other layers, but here we can happily just compute the excluded minors with at most 10 elements for each layer.
There is another key advantage to this approach. A matroid $N$ is a strong stabilizer for representability over a partial field $\mathbb{P}$ if, for every 3connected matroid $M$ that is $\mathbb{P}$representable and has an $N$minor, a representation of $N$ can be uniquely extended to a representation of $M$. (For more about stabilizers, see another of Stefan’s posts.) To begin, $U_{2,5}$ is a strong stabilizer for representability over Hydra5. Furthermore, if $N$ is an excluded minor for representability over Hydra$(i+1)$ that is Hydra$i$representable, where $i < 5$, then $N$ is a strong stabilizer for representability over Hydra$i$ [vZ2009]. From the point of view of running computations, it makes life easier to start from strong stabilizers, so we don’t need to worry about keeping track of inequivalent representations of matroids.
This is the highlevel approach that was taken to find the 10element excluded minors. First, using $U_{2,5}$ as a strong stabilizer, we find the excluded minors for Hydra5representability on at most 10 elements. Of these, keep note of any that are Hydra4 representable: we use as stabilizers at the next step. Once we have all the excluded minors for Hydra4representability on at most 10 elements, we repeat the process: those that are Hydra3representable are used as stabilizers. Note that we need to look at all previous layers: for example, some of the excluded minors for Hydra5representability are Hydra2representable, but not Hydra3 or Hydra4representable; these will also be added to the set of stabilizers when finding excluded minors for Hydra2representability.
To compute the excluded minors for Hydra$i$representability with a given stabilizer minor, the approach taken was fairly naive. (In [BP2021+] we employed fancier optimisations, when computing excluded minors that are several elements larger than the stabilizer, but that is not the case here.) We keep track only of 3connected matroids. We build up the excluded minors one element at a time. Suppose we know the excluded minors of size $n1$ and want to find those of size $n$. We first grow the Hydra$i$ representable matroids with a stabilizer minor, up to size $n$ (for an idea of how you can do this in Sage, I refer you to yet another post of Stefan’s). Then we look at all extensions of the $(n1)$element Hydra$i$representable matroids, and of those that are not Hydra$i$representable, we check they don’t contain a known excluded minor (of size at most $n1$).
Taking this approach we find the excluded minors for Hydra$i$representability on at most 10 elements, for each $i$. Computing these excluded minors becomes, in a sense, a bookkeeping exercise. There are 33 excluded minors for Hydra5representability on at most 10 elements (incidentally, there is quite a nice concise way to describe these). Only 7 of these are Hydra4representable, and these belong to one of just three equivalence classes (I’m getting a bit ahead of myself, but the equivalence is up to duality and $\Delta$$Y$ exchange — I’ll return to this point later on). Using these as seeds, we find there are 63 excluded minors for Hydra4representability on at most 10 elements, and of those that are Hydra3representable, there are 9 equivalence classes. Then things start to get a bit more out of hand: there are 133 excluded minors for Hydra3representability on at most 10 elements, of those that are Hydra2representable, there are 35 equivalence classes; and there are 621 excluded minors for Hydra2representability on at most 10 elements, those that are uniquely GF(5)representable are in one of 147 equivalence classes (!).
Enough buildup: let’s look at how many excluded minors on 10elements there are. The following table shows the number of excluded minors for GF(5)representability of a given size $n$ and rank $r$, when $n \leq 10$. First, note that the numbers on at most nine elements are consistent with those of Mayhew and Royle [MR2006], which is a nice sanity check for the approach taken. The last row of the table, where $n=10$, is new.
$n$ \ $r$ 
2 
3 
4 
5 
6 
7 
8 
total 
7 
1 
5 
5 
1 



12 
8 
– 
2 
92 
2 
– 


96 
9 
– 
9 
219 
219 
9 
– 

456 
10 
– 
1 
130 
1866 
130 
1 
– 
2128 
A list of more than 2000 excluded minors does not seem to be a particularly concise (or elegant) way to describe a class. Are there natural approaches to describe these more concisely? (This was also discussed quite recently in Jim Geelen’s talk.) As a simple example, if a matroid $M$ is an excluded minor, then its dual $M^*$ is as well. Depending on how many selfdual matroids arise as excluded minors, this could reduce the number of matroids to consider by up to a factor of two.
It is also known that the set of excluded minors for representability over a field is closed under $\Delta$$Y$ (and $Y$$\Delta$) exchanges [AO1993], and a generalisation of these operations known as segmentcosegment (and cosegmentsegment) exchanges [OSV2000]. From a matroidal point of view, given a coindependent 3element circuit $T$, a $\Delta$$Y$ exchange is the generalised parallel connection of $M(K_4)$ along $T$. In other words, glue a $M(K_4)$ along a coindependent triangle $T$, and then delete $T$. For example, consider $U_{2,6}$, an excluded minor for GF(4) representability. After performing a single $\Delta$$Y$ exchange we obtain the rank3 matroid $P_6$, after one more $\Delta$$Y$ exchange we obtain $U_{4,6}$; these are also excluded minors for quaternary matroids.
If we consider dualclosed $\Delta$$Y$ equivalence classes, we reduce the numbers as follows:
$n$ 
number of matroids 
number of dualclosed $\Delta$$Y$ equivalence classes 
7 
12 
4 
8 
96 
73 
9 
456 
131 
10 
2128 
920 
total for $n \le 10$ 
2692 
1128 
You might ask why I didn’t instead count dualclosed segmentcosegment equivalence classes. It turns out this doesn’t make much difference, as excluded minors for GF(5) with 4 or 5point lines seem (broadly speaking) to be relatively rare — the only noticeable change would be the merging of two classes on $n=10$ into one (so we’d have 919 classes instead of 920).
It’s all very well using a computer to find these excluded minors, but that is not really the goal in and of itself; the hope is that this data would also be useful in building a better understanding of these excluded minors. The question is what to look for… I’m open to suggestions! And for anyone interested in playing around with these matroids (using Sage, for example), I’m happy to share the data. Perhaps one natural first question is: how many of the excluded minors are not representable over any field? Of the 920 dualclosed $\Delta$$Y$ equivalence classes of 10element excluded minors for GF(5), 513 of the classes consist of nonrepresentable matroids. In other words, 1235 out of 2128 of the 10element matroids are nonrepresentable.
Dyadic matroids
I’m going to switch now to a slightly different, but related, computation, which actually predates the one just discussed. My interest in running computations to find excluded minors first started a few years ago when I was doing a postdoc with Rudi Pendavingh at TU/e, and we were looking to find excluded minors for the class of 2regular matroids up to a certain size. I won’t go into detail about 2regular matroids in this post, but they are closely related to Hydra5representable matroids, and Ben Clark previously posted about ongoing efforts (as of 2016) to find the excluded minors for this class. From an algorithmic point of view, once you have an approach to compute excluded minors for a class of matroids representable over a partial field $\mathbb{P}$, the choice of partial field $\mathbb{P}$ is not important. In other words, it was little effort to adapt the code to find excluded minors for a different partial field.
So after 2regular matroids, we shifted focus to dyadic matroids. For dyadic matroids, the stabilizers of interest are the nonFano matroid, its dual, and $P_8$ (these are excluded minors for nearregular matroids). We were able to compute the excluded minors for dyadic matroids up to 15 elements. For dyadic matroids, there are some advantages compared to the computations described earlier in this post: we can essentially work over the ternary field (for which the Sage matroids library has a number of optimisations), and we consider matroids that are several elements larger than the 7 or 8element stabilizer minor (as touched on earlier, we devised some optimisations that utilise this). The more technical details should one day be available in [BP2021+].
Consider the following matrices:
$A_1 = \begin{pmatrix}
0 & 1 & 1 & 0 & 1 \\
1 & 2 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 2 \\
0 & 0 & 1 & 2 & 1 \\
1 & 1 & 2 & 1 & 0 \\
\end{pmatrix}$
$A_2 = \begin{pmatrix}
2 & 1 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 2 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \\
\end{pmatrix}$
$A_3 = \begin{pmatrix}
2 & 0 & 0 & 2 & 1 & 1 & 2 \\
1 & 2 & 0 & 0 & 2 & 0 & 2 \\
0 & 1 & 2 & 1 & 0 & 0 & 2 \\
0 & 2 & 2 & 0 & 0 & 0 & 2 \\
1 & 0 & 0 & 0 & 1 & 0 & 2 \\
2 & 0 & 0 & 1 & 2 & 1 & 1 \\
1 & 1 & 1 & 2 & 2 & 2 & 0 \\
\end{pmatrix}$
$A_4 = \begin{pmatrix}
2 & 0 & 2 & 1 & 2 & 1 & 0 & 0 \\
2 & 1 & 0 & 2 & 0 & 2 & 2 & 0 \\
2 & 0 & 2 & 0 & 0 & 1 & 0 & 0 \\
2 & 0 & 2 & 2 & 2 & 2 & 2 & 2 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
2 & 1 & 0 & 0 & 0 & 2 & 0 & 0 \\
2 & 0 & 0 & 2 & 2 & 2 & 2 & 0 \\
1 & 0 & 1 & 2 & 1 & 2 & 1 & 1 \\
\end{pmatrix}$
For each $i \in \{1,2,3,4\}$, let $N_i$ be the ternary matroid with representation $[IA_i]$. Note that $N_i$ has 8+2i elements. Each of these matroids is selfdual, and has a pair of disjoint circuithyperplanes.
Theorem [BP2021+]:
The excluded minors for dyadic matroids on at most 15 elements are $U_{2,5}$, $U_{3,5}$, $F_7$, $F_7^*$, $AG(2,3) \backslash e$, $(AG(2,3) \backslash e)^*$, $(AG(2,3) \backslash e)^{\Delta Y}$, $T_8$, $N_1$, $N_2$, and $N_3$. Moreover, $N_4$ is a 16element excluded minor for the class of dyadic matroids.
Note that Rudi Pendavingh had previously done an exhaustive search to find all excluded minors on at most 13 elements (and, in particular, discovered the matroids $N_1$ and $N_2$). $N_3$ was found from our exhaustive computation on up to 15 elements. $N_4$ was found by a “needleinthehaystack” search: we just considered extensions of 15element dyadic matroids that had a disjoint pair of circuit hyperplanes, and found precisely one was an excluded minor.
Open question:
Is there another matroid in the “sequence” $N_1$, $N_2$, $N_3$, $N_4$ of excluded minors for dyadic matroids?
Bibliography:
[AO1993] S. Akkari, J. Oxley. Some Local Extremal Connectivity Results for Matroids. Combinatorics, Probability and Computing 2(4) (1993), 367384.
[BP2021+] N. Brettell, R. Pendavingh. Computing excluded minors for classes of matroids representable over partial fields. In preparation.
[MR2008] D. Mayhew, G. Royle. Matroids with nine elements. J. Combin. Theory Ser. B 98(2) (2008), 415431.
[OSV2000] J. Oxley, C. Semple, D. Vertigan. Generalized $\Delta$$Y$ Exchange and $k$Regular Matroids. J. Combin. Theory Ser. B 79(1) (2000) 165.
[OVW1996] J. Oxley, D. Vertigan, G. Whittle. On inequivalent representations of matroids over finite fields. J. Combin. Theory Ser. B 67(2) (1996) 325–343
[PvZ2010] R.A. Pendavingh, S.H.M. van Zwam. Confinement of matroid representations to subsets of partial fields. J. Combin. Theory Ser. B 100(6) (2010), 510545.
[vZ2009] S.H.M. van Zwam. Partial Fields in Matroid Theory. Ph.D. Thesis, Eindhoven University of Technology, 2009.