This past spring, Jim Geelen and I co-supervised Timothy Wahyudi, an undergraduate researcher who did the actual coding for this project. Using computer searches, we hoped to get a better sense of how the excluded minors for $\text{GF}(5)$-representability are distributed and to see what we could say about their structures. This being a difficult problem, the main resolution was generating the complete list of the rank-$3$ excluded minors. All the excluded minors for $\text{GF}(5)$-representability on up to nine elements have already been determined (in any rank) [MR09], while $U_{2,7}$ is known to be the only rank-$2$ excluded minor. We found that there are a total of eighteen rank-$3$ excluded minors and they have the following distribution.

$n$		Number of $n$-element rank-$3$ excluded minors for $\text{GF}(5)$-representability
$n<7$		$0$
$7$		$5$
$8$		$2$
$9$		$9$
$10$		$1$
$11$		$1$
$n>11$		$0$

The strategy

A naïve approach to finding all the rank-$3$ excluded minors is as follows.

1. Generate all the simple $\text{GF}(5)$-representable matroids of rank $3$.
2. Find all single-element extensions of these matroids.
3. Filter out the extensions that are $\text{GF}(5)$-representable or contain a $U_{2,7}$-minor.
4. Only keep those that are now restriction-minimal.

However, the simple, $\text{GF}(5)$-representable matroids of rank $3$ can have at most $|\text{PG}(2,5)|=31$ elements, so this would be computationally taxing. We do not want to generate matroids that cannot be extended to an excluded minor, so we should avoid using too many elements that do not help prevent possible $\text{GF}(5)$-representations in some way.

As Stefan van Zwam discussed in a previous post, stabilizers help distinguish between inequivalent representations. Recall that a matroid $N$ is a stabilizer for $\text{GF}(5)$-representability when, for each $\text{GF}(5)$-representation $A$ of $N$ and each $3$-connected matroid $M$ containing $N$ as a minor, there is at most one representation of $M$ (up to projective equivalence) that contains $A$ as a submatrix.

Lemma. Let $r\geq 2$. Let $N$ be a $3$-connected stabilizer for $\text{GF}(5)$-representability of rank $r$ and let $M$ be a rank-$r$ excluded minor for $\text{GF}(5)$-representability that contains $N$ as a restriction. For any representation $A$ of $N$, there is some subset $X\subseteq E(M)$ of size at most $r$ such that $A$ does not extend to a representation of $M|E(N)\cup X$.

Proof. Consider a fixed $\text{GF}(5)$-representation $A$ of $N$. For any $e\in E(M)-E(N)$, as $N$ is $3$-connected and has the same rank as $M$, we have that $M|E(N)\cup\{e\}$ is $3$- connected. We may assume that there is a representation of $M|E(N)\cup\{e\}$ of the form $[A|v_e]$ for some vector $v_e$ as otherwise we are done. As $N$ is a stabilizer, this representation extending $A$ is unique up to row operations and column scaling. However, as $N$ is connected and $E(N)$ is spanning, the submatrix $A$ uniquely determines the vector $v_e$ up to scaling.

Now consider the matrix $A’=[A|v_e]_{e\in E(M)-E(N)}$ where we extend $A$ by $v_e$ for each $e\in E(M)-E(N)$. As $M$ is not $\text{GF}(5)$-representable, there is some $X\subseteq E(M)$ of size at most $r$ such that the rank $X$ in $M$ disagrees with the rank of the set of columns of $A’$ indexed by $X$. As the choice of column vectors is unique (up to scaling), $A$ does not extend to a representation of $M|E(N)\cup X$. $\square$

By applying this lemma to each representation of a $3$-connected rank-$r$ stabilizer, we get the following.

Corollary. Let $M$ be a rank-$r$ excluded minor for $\text{GF}(5)$-representability that contains a $3$-connected rank-$r$ stabilizer $N$. Then there is a sequence of matroids $N=N_0,N_1,\dots,N_k=M$ such that $N_{i}$ is a single element extension of $N_{i-1}$ for $i$ in $\{1,\dots,k\}$, and for $i$ in $\{r,r+1,\dots,k\}$ there are strictly fewer inequivalent $\text{GF}(5)$-representations for $N_{i}$ than for $N_{i-r}$.

However, to use this to create a search strategy, it remains to be seen that every rank-$r$ excluded minor for $\text{GF}(5)$-representability actually contains a $3$-connected rank-$r$ stabilizer $N$. Here we can use the following theorem due to Whittle.

Theorem (Whittle [Whi99])

• $U_{2,5}$ and $U_{3,5}$ are stabilizers for $\text{GF}(5)$-representability.
• $U_{2,4}$ is a stabilizer for $\text{GF}(5)$-representability for matroids without a $U_{2,5}$ or a $U_{3,5}$ as a minor.

Furthermore, note that $\text{GF}(5)$-representable matroids without a $U_{2,4}$ minor are $\text{GF}(2)$-representable [Tut58] and have a unique $\text{GF}(5)$-representation [BL76] (see [Oxley] Theorem 6.5.4 and Proposition 6.6.5 respectively). Starting with these facts and using Seymour’s Splitter Theorem [Sey95] (see [Oxley] Corollary 12.2.1), one can check that the following holds.

Lemma. Each $3$-connected matroid with rank $r\geq3$ either

• contains a $U_{3,5}$-minor as a stabilizer,
• does not contain a $U_{3,5}$-minor and contains a minor isomorphic to the three-whirl, $\mathcal{W}^3$, as a stabilizer, or
• does not have a $U_{2,4}$-minor and contains a minor isomorphic to the three-wheel, $\mathcal{W}_3=M(K_4)$, as a stabilizer.

(see also Proposition 12.2.15 and Corollary 12.2.19 in [Oxley]). One can do this more generally to find the list of appropriate $3$-connected rank-$r$ stabilizers for a given $r$.

As excluded minors for $\text{GF}(5)$-representability are $3$-connected, we can use the above lemmas to show that the following approach finds all the rank-$3$ excluded minors.

1. Start with $U_{3,5}$ (six inequivalent representations), $\mathcal{W}^3$ (three inequivalent representations), and $\mathcal{W}_3$ (one inequivalent representation).
2. By keeping track of inequivalent representations while extending matrices, find all $\text{GF}(5)$-representable matroids of rank-$3$ that are never more than $3$ deletions away from a $3$-connected rank-$3$ matroid with strictly more inequivalent $\text{GF}(5)$-representations.
3. Find all single element extensions of these matroids.
4. Filter out the extensions that are $\text{GF}(5)$-representable or contain a $U_{2,7}$.
5. Only keep those that are now restriction-minimal.

The resulting collection of matroids is the set of rank-$3$ excluded minors for $\text{GF}(5)$-representability. I have included a geometric representations for each of them below and brief descriptions of their representabilities. 

The matroids

To avoid ambiguity, lines of the matroid do not cross in the diagram when they are drawn tangent to each other.

• The above matroids are each representable over a field $\mathbb{F}$ if and only if $|\mathbb{F}|\geq 7$. To see non-$\text{GF}(5)$-representability, we can consider intersections of lines in the ambient geometry to force the existence of a $U_{2,7}$-minor.

• These two matroids are each $\mathbb{F}$-representable if and only if $|\mathbb{F}|\geq 7$. To see non-$\text{GF}(5)$-representability, we can consider some of the points “at infinity” and check how we may arrange the remaining points in the affine plane over $\text{GF}(5)$.

For all the remaining examples, one can find three lines (not necessarily disjoint) whose union contains all the points of the matroid. If these lines are to be coincident in a representation we can obtain a system of additive relations, while if they are not we can obtain a system of multiplicative relations. We can check that there are no solutions in $\text{GF}(5)$ for whichever may be the case.

• The four matroids above are also each $\mathbb{F}$-representable if and only if $|\mathbb{F}|\geq 7$.

• The Fano matroid is the Reid geometry of order two and is $\mathbb{F}$-representable if and only if $\mathbb{F}$ has characteristic two.

• The ternary affine plane minus an element is $\mathbb{F}$-representable if and only if either $\mathbb{F}$ has characteristic three or there is a third root of unity.

• The Pappus matroid is $\mathbb{F}$-representable if and only if either $|\mathbb{F}|=4$ or $|\mathbb{F}|\geq 7$.

• None of these are representable over any field and include the non-Pappus matroid (first) and the Reid geometry of order four (middle).

While there seem to be some nice patterns and symmetries here (some of which can be made more obvious with different drawings and groupings), to what extent they generalize or are useful remains to be seen.

References

• [BL76] Brylawski, T.H. and Lucas, D. (1976). Uniquely representable combinatorial geometries. In Teorie combinatorie (Proc. 1973 Internat. Colloq.), 83–104. Accademia Nazionale dei Lincei, Rome.
• [MR08] Mayhew, D. and Royle, G. (2008). Matroids with nine elements. J. Combin. Theory Ser. B 98, 415–431.
• [Oxley] Oxley, J. (2011). Matroid Theory, 2nd edition. Oxford University Press.
• [Sey95] Seymour, P. D. (1995). Matroid minors. In Handbook of combinatorics (eds. R. Graham, M. Grötschel, L. Lovász), 527–550. Elsevier, Amsterdam; MIT Press, Cambridge.
• [Tut58] Tutte, W. T. (1958). A homotopy theorem for matroids, I, II. Trans. Amer. Math. Soc. 88, 144–174.
• [Whi99] Whittle, G. (1999). Stabilizers of classes of representable matroids. J. Combin. Theory Ser. B 77, 39–72.