{"id":3244,"date":"2020-10-26T00:00:00","date_gmt":"2020-10-26T04:00:00","guid":{"rendered":"http:\/\/matroidunion.org\/?p=3244"},"modified":"2020-11-15T19:59:04","modified_gmt":"2020-11-16T00:59:04","slug":"the-rank-3-excluded-minors-for-gf5-representability","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=3244","title":{"rendered":"The rank-3 excluded minors for GF(5)-representability"},"content":{"rendered":"\n

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<\/a>], 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.<\/p>\n\n\n\n

$n$<\/strong><\/td><\/th>Number of $n$-element rank-$3$ excluded minors for<\/strong>
$\\text{GF}(5)$-representability<\/strong><\/td><\/tr><\/thead>
$n<7$<\/td><\/td>$0$<\/td><\/tr>
$7$<\/td><\/td>$5$<\/td><\/tr>
$8$<\/td><\/td>$2$<\/td><\/tr>
$9$<\/td><\/td>$9$<\/td><\/tr>
$10$<\/td><\/td>$1$<\/td><\/tr>
$11$<\/td><\/td>$1$<\/td><\/tr>
$n>11$<\/td><\/td>$0$<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

The strategy<\/h1>\n\n\n\n

A na\u00efve approach to finding all the rank-$3$ excluded minors is as follows.<\/p>\n\n\n\n

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

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

    As Stefan van Zwam discussed in a previous post<\/a>, stabilizers help distinguish between inequivalent representations. Recall that a matroid $N$ is a stabilizer<\/em> 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.<\/p>\n\n\n\n

    Lemma<\/strong>. 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$.<\/em><\/p>\n\n\n\n

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

    Now consider the matrix $A\u2019=[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\u2019$ 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$<\/p>\n\n\n\n

    By applying this lemma to each representation of a $3$-connected rank-$r$ stabilizer, we get the following.<\/p>\n\n\n\n

    Corollary.<\/strong> 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}$.<\/em><\/p>\n\n\n\n

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

    Theorem (Whittle [Whi99<\/a>])<\/strong><\/p>\n\n\n\n