This post is a spiritual successor to Rutger’s post from a few months ago.  In that post, Rutger discussed the rank-3 excluded minors for GF(5)-representability.  Here I’m going to discuss the 10-element 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 10-element 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 3-connected 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 Hydra-1 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 Hydra-5- and Hydra-6-representable 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 Hydra-5-representability and want to find the excluded minors for Hydra-4-representability.  Consider a matroid that has exactly four inequivalent representations over GF(5): it is Hydra-4-representable but not Hydra-5-representable, so it contains an excluded minor for Hydra-5-representability as a minor.  This tells us that once we understand the Hydra-5-representable matroids, we can restrict our attention to matroids that have an $N$-minor, where $N$ is an excluded minor for Hydra-5-representability that is Hydra-4-representable.  In theory, we could attempt to repeat this process at each layer, starting with Hydra-5, then Hydra-4, all the way to Hydra-1, that is, GF(5).  Of course, finding all the excluded minors for Hydra-5 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 3-connected 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 Hydra-5.  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 high-level approach that was taken to find the 10-element excluded minors. First, using $U_{2,5}$ as a strong stabilizer, we find the excluded minors for Hydra-5-representability on at most 10 elements.  Of these, keep note of any that are Hydra-4 representable: we use as stabilizers at the next step.  Once we have all the excluded minors for Hydra-4-representability on at most 10 elements, we repeat the process: those that are Hydra-3-representable are used as stabilizers.  Note that we need to look at all previous layers: for example, some of the excluded minors for Hydra-5-representability are Hydra-2-representable, but not Hydra-3- or Hydra-4-representable; these will also be added to the set of stabilizers when finding excluded minors for Hydra-2-representability.

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 3-connected matroids. We build up the excluded minors one element at a time. Suppose we know the excluded minors of size $n-1$ 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 $(n-1)$-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 $n-1$).

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 book-keeping exercise.  There are 33 excluded minors for Hydra-5-representability on at most 10 elements (incidentally, there is quite a nice concise way to describe these).  Only 7 of these are Hydra-4-representable, 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 Hydra-4-representability on at most 10 elements, and of those that are Hydra-3-representable, there are 9 equivalence classes.  Then things start to get a bit more out of hand: there are 133 excluded minors for Hydra-3-representability on at most 10 elements, of those that are Hydra-2-representable, there are 35 equivalence classes; and there are 621 excluded minors for Hydra-2-representability on at most 10 elements, those that are uniquely GF(5)-representable are in one of 147 equivalence classes (!).

Enough build-up: let’s look at how many excluded minors on 10-elements 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.

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 self-dual 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 segment-cosegment (and cosegment-segment) exchanges [OSV2000].  From a matroidal point of view, given a coindependent 3-element 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 rank-3 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 dual-closed $\Delta$-$Y$ equivalence classes, we reduce the numbers as follows:

You might ask why I didn’t instead count dual-closed segment-cosegment equivalence classes. It turns out this doesn’t make much difference, as excluded minors for GF(5) with 4- or 5-point 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 dual-closed $\Delta$-$Y$ equivalence classes of 10-element excluded minors for GF(5), 513 of the classes consist of non-representable matroids.  In other words, 1235 out of 2128 of the 10-element matroids are non-representable.

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 post-doc with Rudi Pendavingh at TU/e, and we were looking to find excluded minors for the class of 2-regular matroids up to a certain size.  I won’t go into detail about 2-regular matroids in this post, but they are closely related to Hydra-5-representable 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 2-regular matroids, we shifted focus to dyadic matroids.  For dyadic matroids, the stabilizers of interest are the non-Fano matroid, its dual, and $P_8$ (these are excluded minors for near-regular 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 8-element 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 $[I|A_i]$.  Note that $N_i$ has 8+2i elements.  Each of these matroids is self-dual, and has a pair of disjoint circuit-hyperplanes.

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 16-element 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 “needle-in-the-haystack” search: we just considered extensions of 15-element 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), 367-384.
[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), 415-431.
[OSV2000] J. Oxley, C. Semple, D. Vertigan. Generalized $\Delta$-$Y$ Exchange and $k$-Regular Matroids. J. Combin. Theory Ser. B 79(1) (2000) 1-65.
[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), 510-545.
[vZ2009] S.H.M. van Zwam. Partial Fields in Matroid Theory. Ph.D. Thesis, Eindhoven University of Technology, 2009.