{"id":3815,"date":"2021-02-22T17:48:00","date_gmt":"2021-02-22T22:48:00","guid":{"rendered":"http:\/\/matroidunion.org\/?p=3815"},"modified":"2021-02-22T18:34:32","modified_gmt":"2021-02-22T23:34:32","slug":"the-excluded-minors-for-gf5-representability-on-10-elements","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=3815","title":{"rendered":"The excluded minors for GF(5)-representability on 10 elements"},"content":{"rendered":"\n

This post is a spiritual successor to Rutger’s post from a few months ago<\/a>.\u00a0 In that post, Rutger discussed the rank-3 excluded minors for GF(5)-representability.\u00a0 Here I’m going to discuss the 10-element excluded minors for GF(5)-representability.<\/p>\n

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].\u00a0 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.\u00a0 For those unfamiliar with partial fields, Stefan previously posted about them, in detail, see part 1<\/a>, part 2<\/a>, and part 3<\/a>.\u00a0 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.\u00a0 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).\u00a0 For simplicity, assume we only care about 3-connected matroids having a $U_{2,5}$- or $U_{3,5}$-minor.\u00a0 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).\u00a0 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].\u00a0 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].\u00a0 So there are really five layers to the Hydra partial field hierarchy.<\/p>\n

Suppose we know all the excluded minors for Hydra-5-representability and want to find the excluded minors for Hydra-4-representability.\u00a0 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.\u00a0 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.\u00a0 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).\u00a0 Of course, finding all<\/em> 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.\u00a0<\/p>\n

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<\/a>.) To begin, $U_{2,5}$ is a strong stabilizer for representability over Hydra-5.\u00a0 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].\u00a0 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.<\/p>\n

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.\u00a0 Of these, keep note of any that are Hydra-4 representable: we use as stabilizers at the next step.\u00a0 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.\u00a0 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.<\/p>\n

To compute the excluded minors for Hydra-$i$-representability with a given stabilizer minor, the approach taken was fairly naive.\u00a0 (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.)\u00a0 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<\/a>). 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$).<\/p>\n

Taking this approach we find the excluded minors for Hydra-$i$-representability on at most 10 elements, for each $i$.\u00a0 Computing these excluded minors becomes, in a sense, a book-keeping exercise.\u00a0 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).\u00a0 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).\u00a0 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.\u00a0 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 (!).<\/p>\n

Enough build-up: let’s look at how many excluded minors on 10-elements there are.\u00a0 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$.\u00a0 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.<\/p>\n\n\n\n\n\n\n\n
$n$ \\ $r$<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n7<\/td>\n8<\/td>\ntotal<\/td>\n<\/tr>\n
7<\/td>\n1<\/td>\n5<\/td>\n5<\/td>\n1<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n12<\/td>\n<\/tr>\n
8<\/td>\n–<\/td>\n2<\/td>\n92<\/td>\n2<\/td>\n–<\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n96<\/td>\n<\/tr>\n
9<\/td>\n–<\/td>\n9<\/td>\n219<\/td>\n219<\/td>\n9<\/td>\n–<\/td>\n\u00a0<\/td>\n456<\/td>\n<\/tr>\n
10<\/td>\n–<\/td>\n1<\/td>\n130<\/td>\n1866<\/td>\n130<\/td>\n1<\/td>\n–<\/td>\n2128<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

A list of more than 2000 excluded minors does not seem to be a particularly concise (or elegant) way to describe a class.\u00a0 Are there natural approaches to describe these more concisely?\u00a0 (This was also discussed quite recently in Jim Geelen’s talk<\/a>.)\u00a0 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.<\/p>\n

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].\u00a0 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$.\u00a0 For example, consider $U_{2,6}$, an excluded minor for GF(4) representability.\u00a0 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.<\/p>\n

If we consider dual-closed $\\Delta$-$Y$ equivalence classes, we reduce the numbers as follows:<\/p>\n\n\n\n\n\n\n\n\n
$n$<\/td>\nnumber of matroids<\/td>\nnumber of dual-closed $\\Delta$-$Y$ equivalence classes<\/td>\n<\/tr>\n
7<\/td>\n12<\/td>\n4<\/td>\n<\/tr>\n
8<\/td>\n96<\/td>\n73<\/td>\n<\/tr>\n
9<\/td>\n456<\/td>\n131<\/td>\n<\/tr>\n
10<\/td>\n2128<\/td>\n920<\/td>\n<\/tr>\n
total for $n \\le 10$<\/td>\n2692<\/td>\n1128<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

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).<\/p>\n

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.\u00a0 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.\u00a0 Perhaps one natural first question is: how many of the excluded minors are not representable over any field?\u00a0 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.\u00a0 In other words, 1235 out of 2128 of the 10-element matroids are non-representable.<\/p>\n

\n

Dyadic matroids<\/h2>\n

I’m going to switch now to a slightly different, but related, computation, which actually predates the one just discussed.\u00a0 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.\u00a0 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<\/a> about ongoing efforts (as of 2016) to find the excluded minors for this class.\u00a0 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.\u00a0 In other words, it was little effort to adapt the code to find excluded minors for a different partial field.<\/p>\n

So after 2-regular matroids, we shifted focus to dyadic matroids.\u00a0 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).\u00a0 We were able to compute the excluded minors for dyadic matroids up to 15 elements.\u00a0 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+].<\/p>\n

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}$<\/p>\n

$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}$<\/p>\n

$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}$<\/p>\n

$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}$<\/p>\n

For each $i \\in \\{1,2,3,4\\}$, let $N_i$ be the ternary matroid with representation $[I|A_i]$.\u00a0 Note that $N_i$ has 8+2i elements.\u00a0 Each of these matroids is self-dual, and has a pair of disjoint circuit-hyperplanes.<\/p>\n

Theorem [BP2021+]:<\/strong>
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$.\u00a0 Moreover, $N_4$ is a 16-element excluded minor for the class of dyadic matroids.<\/p>\n

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$).\u00a0 $N_3$ was found from our exhaustive computation on up to 15 elements.\u00a0 $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.<\/p>\n

Open question:<\/strong>
Is there another matroid in the “sequence” $N_1$, $N_2$, $N_3$, $N_4$ of excluded minors for dyadic matroids?<\/p>\n

\n

Bibliography:<\/strong><\/p>\n

[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\u2013343
[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.<\/p>\n","protected":false},"excerpt":{"rendered":"

This post is a spiritual successor to Rutger’s post from a few months ago.\u00a0 In that post, Rutger discussed the rank-3 excluded minors for GF(5)-representability.\u00a0 Here I’m going to discuss the 10-element excluded minors for GF(5)-representability. Recall that the excluded … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-3815","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/3815","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3815"}],"version-history":[{"count":27,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/3815\/revisions"}],"predecessor-version":[{"id":3842,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/3815\/revisions\/3842"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3815"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3815"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3815"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}