Matroids representable over the Hydra-5 and 2-regular partial fields.

Guest post by Ben Clark.

1. Introduction

This post is an informal discussion of an ongoing project to find the excluded minors for the classes of matroids that arise from two partial fields, the Hydra-5 partial field and the 2-regular partial field. Stefan’s earlier posts on partial fields and stabilizers are highly recommended as background.

2. The Classes

The Hydra-5 partial field, $\mathbb{H}_5$, was introduced by Pendavingh and Van Zwam [PZ10]. The class of $\mathbb{H}_5$-representable matroids can essentially be thought of as the class of matroids having six inequivalent representations over $\text{GF}(5)$. The excluded minors for this class of matroids are the first step in a 5-step process to find the excluded minors for the class of $\text{GF}(5)$-representable matroids, as described in [MWZ12].

The 2-regular partial field, $\mathbb{U}_2$, was introduced by Semple [S97]. Representations over this partial field are the natural generalisation of `totally unimodular’ and `totally near-unimodular’ representations over the regular and near-regular partial fields. It is therefore natural to ask if $\mathbb{U}_2$ captures the class of matroids representable over all fields of size at least four, but sadly that’s not the case. However, we do expect the excluded minors for the class of $\mathbb{U}_2$-representable matroids will shed light on the following problem.

Problem 1. Find the partial field $\mathbb{P}$ such that the set of $\mathbb{P}$-representable matroids is exactly the set of matroids representable over $\text{GF}(4)$ and all larger fields.

The classes of matroids that arise from $\mathbb{H}_5$ and $\mathbb{U}_2$ are closely related (the latter is a subset of the former), and it seems that any differences in the excluded-minor analyses can be confined to finite case checks.

3. Inequivalent representations

Broadly speaking, we follow the strategy used in Geelen, Gerards and Kapoor’s excluded-minor characterisation of the $\text{GF}(4)$-representable matroids [GGK00]. The first step is to construct a candidate matrix for an excluded minor $M$. That is, a candidate for a representation of $M$ that we construct by piecing together representations for some of its minors, say $M\backslash a$ and $M\backslash b$. The construction of this candidate representation is complicated by the possibility of inequivalent representations, that is, the minors $M\backslash a$ and $M\backslash b$ could have representations that we cannot piece together.

The way around the problem of inequivalent representations is to keep a certain minor and sufficient connectivity. We have a class of $\mathbb{P}$-representable matroids for some fixed partial field $\mathbb{P}$. A matroid $N$ is called a strong stabilizer for the class of $\mathbb{P}$-representable matroids if every $\mathbb P$-representation of $N$ extends uniquely to a $\mathbb{P}$-representation of any 3-connected $\mathbb{P}$-representable matroid having $N$ as a minor. In [GGK00], the strong stabilizer is $U_{2,4}$. For the partial fields $\mathbb{U}_5$ and $\mathbb{U}_2$, the strong stabilizer is $U_{2,5}$ (and its dual $U_{3,5}$).

We can therefore construct a candidate matrix $A$ for the excluded minor $M$. Since $M$ is an excluded minor, there must be some difference between the subdeterminants of $A$ and the corresponding subsets of $M$. In fact, we can choose $A$ so that this difference is certified by a $2\times 2$ subdeterminant of $A$ (see [MWZ12]). We call the corresponding set of elements an incriminating set for $(M,A)$.

4. Fragility

Since an excluded minor $M$ is minimal with respect to being non-representable, we deduce that there are no elements that can be removed (in the right way relative to the candidate matrix $A$) keeping all three of: the strong stabilizer $N$ minor, sufficient connectivity, and the incriminating set. Considering only the elements that are required to keep the $N$-minor, it follows that $M$ has some minor $M’$ with the property that $M’\backslash e$ or $M’/e$ has no $N$-minor for every element $e$ of $M’$. Matroids with this property are said to be $N$-fragile, and we can think of them as the foundation for building excluded minors.

In [GGK00], it is shown that the $\text{GF}(4)$-representable $U_{2,4}$-fragile matroids are whirls. Here, we are interested in the structure of the $\mathbb{H}_5$- and $\mathbb{U}_2$-representable $\{U_{2,5}, U_{3,5}\}$-fragile matroids.

A matroid has path width $3$ if there is an ordering $(e_1, e_2, \ldots, e_n)$ of its ground set such that $\{e_1, \ldots, e_t\}$ is $3$-separating for all $t$. Gluing a wheel to $M$ is the process of taking the generalized parallel connection of $M$ with $M(\mathcal{W}_n)$ along a triangle $T$, and deleting any subset of $T$ containing the rim element. We proved the following.

Theorem 1. [CMWZ16] Let $\mathbb{P} \in \{\mathbb{H}_5, \mathbb{U}_2\}$. Let $M$ be a $3$-connected $\{U_{2,5}, U_{3,5}\}$-fragile $\mathbb{P}$-representable matroid with $|E(M)| \geq 10$. Then either

  1. $M$ or $M^*$ can be obtained by gluing up to three wheels to $U_{2,5}$; or
  2. $M$ has path width $3$.

In fact, we can describe the structure of the matroids in this class in much more detail, using the concept of generalized $\Delta$-$Y$ exchange.

The idea of the proof of Theorem 1 is to bound the size of a minimal counterexample to at most 12 elements, then obtain a contradiction by finding all of the $\mathbb{H}_5$-representable $\{U_{2,5}, U_{3,5}\}$-fragile matroids up to 12 elements and showing they have the right structure. The exhaustive search was made feasible by the development of Sage Matroid.

5. Further work

The foremost issue is another fragility problem. We would like to use Theorem 1 to determine the minimal $\{U_{2,5}, U_{3,5}\}$-fragile $\mathbb{P}$-representable matroids that could be used to build an excluded minor. This is relatively simple for whirls in the GF$(4)$ case, and also for the matroids in the first case of Theorem 1, using the structure to find `pivots’ in all but the smallest cases. However, there are families of fragile matroids of path width $3$ where these pivoting arguments are unsuccessful. These families of matroids have a `flan’-type path of $3$-separations.

Beyond that, there is an intertwining problem to solve to bridge the gap from the fragile minor to the incriminating set. This is attacked using blocking sequences in [GGK00]. An approach that we hope will simplify the problem is to make stronger connectivity assumptions on $M\backslash a,b$. We proved the following.

Theorem 2. [COSW16] Let $M$ be a sufficiently large excluded minor for the class of matroids representable over $\mathbb{H}_5$ or $\mathbb{U}_2$. Then $M$ has a $\{U_{2,5}, U_{3,5}\}$-minor, and if $M$ has a pair of elements $a,b$ such that $M\backslash a,b$ is $3$-connected with a $\{U_{2,5}, U_{3,5}\}$-minor, then $M\backslash a,b$ is a $\{U_{2,5}, U_{3,5}\}$-fragile matroid.

Roughly, the strategy for proving Theorem 2 is to assume there are elements that are `not fragile’, that is, elements we can remove to keep the stabilizer minor and the incriminating set. Removing such elements must destroy the $3$-connectivity, so we are able to deduce that $M\backslash a,b$ has a certain path of $3$-separations. Analysing this structure we find pivots if $M\backslash a,b$ is sufficiently large.

To date, we have no guarantee that a $3$-connected deletion pair exists, but progress towards finding such a pair is happening. Williams [W15] proved the following theorem. We say that a pair $a,b$ of elements of a 3-connected matroid $M$ is detachable if either $M\backslash a,b$ of $M/a,b$ is 3-connected.

Theorem 3. [W15] Let $M$ be a $3$-connected matroid with $|E(M)|\geq 12$. Then one of the following holds.

  1. $M$ is a spike; or
  2. $M$ contains a detachable pair; or
  3. There is a matroid obtained by performing a single $\Delta$-$Y$ operation on$M$ that contains a detachable pair.

The next step in this direction is to obtain a `splitter’ analogue of Theorem 3 that preserves a copy of a minor $N$.

References

[COSW16] B.Clark, J. Oxley, C. Semple, G. Whittle. Excluded minors are almost fragile. Submitted.

[CMWZ16] B.Clark, D. Mayhew, G. Whittle, S.H.M. van Zwam. The structure of $\{U_{2,5}, U_{3,5}\}$-fragile matroids. SIAM J. Discrete Math., to appear.

[GGK00] J. Geelen, A.M.H. Gerards, A. Kapoor. The Excluded Minors for GF(4)-Representable Matroids. J. Combin. Theory Ser. B, 79, 247-299, 2000.

[MWZ12] D. Mayhew, G. Whittle, S.H.M. van Zwam. Stability, Fragility, and Rota’s Conjecture. J. Combin. Theory Ser. B, 102(3):760-783, 2012.

[PZ10] R.A. Pendavingh, S.H.M. van Zwam. Confinement of matroid representations to subsets of partial fields. J. Combin. Theory Ser. B, 100(6):510-545, 2010.

[S99] C. Semple. On maximum-sized k-regular matroids. Graphs Combin., 15, 441-462, 1999.

[W15] A. Williams. Detachable pairs in 3-connected matroids.. PhD thesis, Victoria University of Wellington, 2015.

Leave a Reply

Your email address will not be published. Required fields are marked *