About Nick Brettell

I'm a postdoc at Victoria University of Wellington working primarily on matroid structure theory.

The excluded minors for GF(5)-representability on 10 elements

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.

$n$ \ $r$ 2 3 4 5 6 7 8 total
7 1 5 5 1       12
8 2 92 2     96
9 9 219 219 9   456
10 1 130 1866 130 1 2128

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:

$n$ number of matroids number of dual-closed $\Delta$-$Y$ equivalence classes
7 12 4
8 96 73
9 456 131
10 2128 920
total for $n \le 10$ 2692 1128

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 \\

$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 \\

$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 \\

$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 \\

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?


[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.

Exceptional matroids in chain theorems

At the end of November 2017, the Tutte Centenary Retreat was held.  32 researchers gathered in Creswick Australia to work on problems in three areas where Tutte made seminal contributions. One of those three areas was Matroid Structure Theory: nine of us (Rutger Campbell, Deborah Chun, Tara Fife, Kevin Grace, Dillon Mayhew, James Oxley, Charles Semple, Geoff Whittle, and myself) split into two groups to work on some carefully curated problems in this area.  In this post, I’m going to talk about matroids where certain subsets of the ground set appear in circuits and cocircuits of certain sizes — mostly work that originated during this week in Creswick — as well as some related work and open problems in the area.

Rather than getting into any detail of the proofs, my aim with this post is to give an overview of the motivation (from a connectivity-centric point of view), the results, and give some open questions and conjectures on the topic.  Essentially, most of the results follow from repeated use of orthogonality: the fact that a circuit and cocircuit of a matroid cannot intersect in a single element.

To start with, let’s consider matroids where every $t$-element subset of the ground set appears in an $\ell$-element circuit and an $\ell$-element cocircuit; for brevity, call these $(t,\ell)$-matroids.

For example, wheels and whirls are (1,3)-matroids: every element in a wheel or whirl appears in a triangle (a 3-element circuit) and a triad (a 3-element cocircuit).  Excluding the rank-2 wheel, these matroids are 3-connected, and, due to the triangles and triads, deleting or contracting any single element results in a matroid that is no longer 3-connected.  Tutte’s Wheels-and-Whirls Theorem states that these are in fact the only 3-connected matroids with no single-element deletion or contraction preserving 3-connectedness.

More generally, one reason why someone might be interested in $(t,\ell)$ matroids is that they would appear as exceptional matroids in chain theorems (results like the Wheels-and-Whirls theorem). For example, any 4-connected (1,4)-matroid has no single-element deletion or contraction that is 4-connected (due to the 4-element circuits and cocircuits), and any 3-connected (2,4)-matroid has no pair of elements whose deletion or contraction remains 3-connected (here we are allowed only to delete both elements, or contract both elements). These may or may not be the only matroids with this property, but they provide a starting point.

(2,4)-matroids, a.k.a. spikes

So what can we say about (2,4)-matroids? Joel Miller [Miller2014] showed the following:

Let $M$ be a matroid with $|E(M)| \ge 13$.  Then $M$ is a (2,4)-matroid if and only if $M$ is a spike.

One way of defining a spike (useful for the purposes of this post) is as a matroid with a partition into pairs $(X_1,X_2,\ldots,X_t)$, for some $t \ge 3$, such that for all distinct $i,j \in [t]$, $X_i \cup X_j$ is both a circuit and a cocircuit.  Note that all “spikes” in this post are what are sometimes referred to as tipless spikes.

Miller also showed that the bound of 13 is tight, and described all matroids with the (2,4)-property when $|E(M)| \le 12$.

As I mentioned earlier, since spikes are (2,4)-matroids, they have no pair of elements whose deletion or contraction remains 3-connected.  In fact, Alan Williams [Williams2015] showed that the only 3-connected matroids having this connectivity property, with $|E(M)| \ge 13$, and no triangles or triads, are spikes.  So in this case, (2,4)-matroids are the only exceptional matroids appearing in a chain theorem for removing a pair of elements from a 3-connected matroid with no triangles or triads, and retaining 3-connectivity (the caveat being the “no triangles or triads” condition: I’ll touch more on this in the section after next).

$(t,2t)$-matroids, a.k.a. $t$-spikes

With Rutger Campbell, Deborah Chun, Kevin Grace, and Geoff Whittle [BCCGW2018], we generalised Miller’s result as follows.

Let $M$ be a matroid, and let $t$ be a positive integer. For each $t$, there exists an $n_t$ such that if $M$ is a matroid with the $(t,2t)$-property and $|E(M)| \ge n_t$, then $M$ has a partition into pairs such that the union of any $t$ pairs is both a circuit and a cocircuit.

We call a matroid a $t$-spike if it has a partition $\pi$ into pairs such that the union of any $t$ pairs is both a circuit and a cocircuit.

The infinite family of $t$-spikes is a natural class of $(t,\ell)$-matroids to consider: we also showed there are only finitely many $(t,\ell)$-matroids for $\ell < 2t$.  Note that spikes are 2-spikes, and it is not hard to show that 1-spikes are matroids obtained by taking direct sums of $U_{1,2}$.  $t$-spikes share some well-known properties of spikes: A $t$-spike $M$ with $r$ legs has rank $r$ (where a leg is one of the pairs in the partition $\pi$), and, when $r$ is sufficiently large, $M$ is $(2t-1)$-connected.  Moreover, the partition $\pi$ associated with a $t$-spike naturally gives rise to crossing $(2t-1)$-separations (for those familiar with flowers, an appropriate concatenation of $\pi$ is a $(2t-1)$-anemone, following the terminology of [AO2008]).

A $(t+1)$-spike $M_2$ can be obtained from a $t$-spike $M_1$ (with sufficiently many legs), by the following construction.  Recall that $M_1’$ is an elementary quotient of $M_1$ if there is some single-element extension $M_1^+$ of $M_1$ by an element $e$ such that $M_1^+/e = M_1’$.  First, take an elementary quotient of the $t$-spike $M_1$ such that none of the $2t$-element cocircuits (from the union of $t$ legs) are preserved. That is, extend $M_1$ by an element $e$ in such a way that the extension does not preserve any of the $2t$-element cocircuits, and then contract $e$. We then repeat this process in the dual: this corresponds to taking an elementary lift such that none of the $2t$-element circuits are preserved. The resulting matroid is a $(t+1)$-spike.  Note that one option for the quotient is to simply truncate (i.e. take a free extension by $e$, and then contract $e$) but there may be others.
For the purposes of this post, I’ll refer to this operation as an inflation of a $t$-spike.  We showed, in [BCCGW2018], that for $t \ge 1$, any $(t+1)$-spike with $r$ legs can be obtained from a $t$-spike with $r$ legs, by an inflation.

Spikes are ubiquitous in matroid theory; perhaps $t$-spikes may also be an interesting family of matroids.


Recall that spikes (i.e. (2,4)-matroids) are the only 3-connected triangle-and-triad-free matroids with no pair of elements whose deletion or contraction preserves 3-connectivity, when we restrict our attention to matroids on at least 13 elements.  What if we want to remove the “triangle-and-triad-free” condition; what additional structures arise? (*)
Certainly wheels and whirls (i.e. (1,3)-matroids) for one, but this is not all.  Another example is any matroid where every pair of elements is in a 4-element circuit, and every element is in a triad.

Say that $M$ is a $(t_1,\ell_1,t_2,\ell_2)$-matroid if every $t_1$-element set is in an $\ell_1$-element circuit, and every $t_2$-element set is in an $\ell_2$-element cocircuit (the $(t,\ell)$-matroids considered earlier have $t_1=t_2$ and $\ell_1=\ell_2$).  James Oxley, Simon Pfeil, Charles Semple and Geoff Whittle [OPSW2018] showed the following:

For $k=3$ or $k=4$, a $k$-connected matroid with $|E(M)| \ge k^2$ is a $(2,4,1,k)$-matroid if and only if $M \cong M(K_{k,n})$ for some $n \ge k$.

So $M(K_{3,n})$ and $M^*(K_{3,n})$ are answers to (*). But there are other structures that arise that don’t fit the $(t_1,\ell_1,t_2,\ell_2)$-matroid framework, that I won’t go into (for more details, see [BWW2018, Conjecture 7.5]; a conjectured answer to (*)).

Apart from the [OPSW2018] result and the case where $t_1 = t_2$ and $\ell_1 = \ell_2$, these $(t_1,\ell_1,t_2,\ell_2)$-matroids have had little attention, as far as I know.  We conjecture the following in [BCCGW2018]:

Any sufficiently large $(t_1,2t_1,t_2,2t_2)$-matroid has a partition into pairs such that the union of any $t_1$ pairs is a circuit, and the union of any $t_2$ pairs is a cocircuit.

$t$-cyclic matroids

If the removing-sets-of-size-$t$-style chain theorems are a bit far-fetched for your taste, I’ll now attempt to return to more traditional single-element deletion/contractions, in a slightly roundabout way.

It seems that obtaining a single-element chain theorem for 4-connectivity in the style of Tutte’s Wheels-and-Whirls Theorem has its difficulties (to put it lightly) — see, for example, [CMO2011] for internally 4-connected binary matroids.

Even if we just consider 4-connected (1,4)-matroids, which we know are matroids with no single-element deletion or contraction that preserves 4-connectedness, this seems like a potentially wild class: it includes $M(K_{4,n})$ and $M^*(K_{4,n})$ for any $n \ge 4$; cycle matroids of grids; or, more generally, take the cycle matroid of any 4-connected 4-regular graph with no 3-cycles, but every edge is in a 4-cycle.

Recall the inflation operation, which we used to obtain a $(t+1)$-spike from a $t$-spike. Using essentially the same operation, we see that (1,6)-matroids are at least as wild as (1,4)-matroids.  (I say “essentially the same” here because now we require that the elementary quotient/lift does not preserve the $2t$-element circuits/cocircuits corresponding to consecutive elements in the cyclic ordering.)  So any horrors from (1,4)-matroids extend to (1,2t)-matroids for integers $t > 2$.  I still reserve some small amount of hope for $(1,2t+1)$-matroids, for $t \ge 2$.  But, in general, characterising $(1,t)$-matroids seems difficult, so let’s first look at doing something easier.

Wheels and whirls (that is, (1,3)-matroids) also have the property that there is a cyclic ordering on the elements such that every pair of consecutive elements in the ordering is contained in a triangle, and contained in a triad.

We say that a matroid has the cyclic $(t-1,t)$-property if there is an ordering $\sigma$ of the ground set such that every set of $t-1$ consecutive elements in $\sigma$ is contained in a $t$-element circuit and a $t$-element cocircuit.

So wheels and whirls have the cyclic (2,3)-property.  Note also that swirls and spikes (i.e. 2-spikes) have the (3,4)-cyclic property.  In fact, $t$-spikes have the $(2t-1,2t)$-cyclic property.

Together with Deborah Chun, Tara Fife, and Charles Semple, we proved a characterisation of matroids with the $(t-1,t)$-cyclic property [BCFS2018].  Before I state this, let me give some intuition.  Essentially, the result shows that one can think of wheels and whirls as a canonical example of matroids with the $(t-1,t)$-property when t is odd; and swirls as a canonical example when $t$ is even — at least, with regards to how the 3- or 4-element circuits/cocircuits appear in either case.  These matroids have not only an ordering that certifies they are $(t-1,t)$-cyclic, but an ordering with a stronger property: for whirls and whirls, any set of $t$ consecutive elements in the ordering is either a (coindependent) circuit or (independent) cocircuit, and these alternate; or for swirls, each set of $t$ consecutive elements in the ordering alternates between being both a circuit and a cocircuit, and being independent and coindependent.

We say that a matroid $M$ is $t$-cyclic if there is an ordering $(e_1,e_2,\ldots,e_n)$ of $E(M)$ such that, when $t$ is odd, each set of $t$-consecutive elements $\{e_i,\ldots,e_{i+t-1}\}$ is a (coindependent) circuit when $i$ is odd, and a (independent) cocircuit when $i$ is even; and when $t$ is even, each set of $t$-consecutive elements $\{e_i,\ldots,e_{i+t-1}\}$ is a circuit and a cocircuit when $i$ is odd (and is independent and coindependent when $i$ is even).  (Indices are interpreted modulo n.)

Theorem [BCFS2018]:
Let $M$ be a matroid with the $(t-1,t)$-property, where $t \ge 3$ and $n \ge 6t-10$. Then $M$ is $t$-cyclic.

A $t$-cyclic matroid with rank $r$ has $2r$ elements, and $t$-cyclic matroids have crossing $t$- or $(t-1)$-separations (when $t$ is odd or even respectively) that can be described in terms of flowers. (For those familiar with flowers: when $t$ is odd, these are daisies; when $t$ is even it is possible, depending on the matroid, to have either daisies or anemones.)  One interesting thing to observe is the effect of the parity of $t$.

We can use the construction referred to as inflation to obtain $(t+2)$-cyclic matroids from $t$-cyclic matroids. Maybe we can get all $t$-cyclic matroids this way:

Conjecture [BCFS2018]:
Let M be a $t$-cyclic matroid for some $t \ge 2$.
If $t$ is even, then M can be obtained from a spike or a swirl by a sequence of inflations.
If $t$ is odd, then M can be obtained from a wheel or a whirl by a sequence of inflations.

I would be surprised if the odd $t$ case of this conjecture does not hold; I am a bit less confident about the case where $t$ is even.

If you’ve made it this far in the post, the reward is a potentially foolhardy conjecture or two.

As touched on earlier, I think perhaps there is some hope for a “nice” characterisation of $(1,t)$-matroids for odd $t \ge 5$.  Here is an optimistic conjecture:

Let $t$ be an odd integer, with $t \ge 3$.  There exists an $n_t$ such that whenever $|E(M)| \ge n_t$, $M$ is $t$-cyclic if and only if $M$ is a $(1,t)$-matroid.

In fact, I’m not even aware of sporadic examples.

For odd t, does there exist a matroid $M$ where every element is in a $t$-circuit and $t$-cocircuit, but $M$ is not $t$-cyclic?


[AO2008] J. Aikin, J. Oxley. The structure of crossing separations in matroids. Adv. in Appl. Math. 41 (2008), 10-26.
[BCCGW2018] N. Brettell, R. Campbell, D. Chun, K. Grace, G. Whittle. On a generalisation of spikes. arXiv:1804.06959.
[BCFS2018] N. Brettell, D. Chun, T. Fife, C. Semple. Matroids with a cyclic arrangement of circuits and cocircuits. arXiv:1806.03625.
[BWW2018] N. Brettell, G. Whittle, A. Williams.  N-detachable pairs in 3-connected matroids III: the theorem. arXiv:1804.06588.
[CMO2011] C. Chun, D. Mayhew, J. Oxley. A chain theorem for internally 4-connected binary matroids. J. Combin. Theory Ser. B 101 (2011), 141-189.
[Miller2014] J. Miller. Matroids in which every pair of elements belongs to a 4-circuit and a 4-cocircuit. M.Sc. thesis, Victoria University of Wellington, 2014.
[OPSW2018] J. Oxley, S. Pfeil, C. Semple, G. Whittle. Matroids with many small circuits and cocircuits. Submitted.
[Williams2015] A. Williams. Detachable pairs in 3-connected matroids. Ph.D. thesis, Victoria University of Wellington, 2015.