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:

Theorem:
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.

Theorem:
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.


$(t_1,\ell_1,t_2,\ell_2)$-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:

Theorem:
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]:

Conjecture:
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:

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.

Question:
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?

Bibliography:

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

One thought on “Exceptional matroids in chain theorems

  1. I’m sorry, I’m having some trouble localizing the unlinked papers in the bibliography. Could you please add links to those as well? Thanks!

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.