{"id":2394,"date":"2018-10-29T13:45:01","date_gmt":"2018-10-29T17:45:01","guid":{"rendered":"http:\/\/matroidunion.org\/?p=2394"},"modified":"2018-10-31T11:33:50","modified_gmt":"2018-10-31T15:33:50","slug":"exceptional-matroids-in-chain-theorems","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=2394","title":{"rendered":"Exceptional matroids in chain theorems"},"content":{"rendered":"

At the end of November 2017, the Tutte Centenary Retreat<\/a>\u00a0was held.\u00a0\u00a032 researchers gathered in Creswick Australia to work on problems in three areas\u00a0where Tutte made seminal contributions. One of those three areas was Matroid\u00a0Structure Theory: nine of us (Rutger Campbell, Deborah Chun, Tara Fife, Kevin Grace, Dillon Mayhew, James Oxley, Charles Semple, Geoff Whittle, and myself)\u00a0split into two groups to work on some carefully curated problems in this area.\u00a0\u00a0In this post, I’m going to talk about matroids where certain subsets of the\u00a0ground set appear in circuits and cocircuits of certain sizes — mostly work\u00a0that originated during this week in Creswick — as well as some related work\u00a0and open problems in the area.<\/p>\n

Rather than getting into any detail of the proofs, my aim with this post is to\u00a0give an overview of the motivation (from a connectivity-centric point of\u00a0view), the results, and give some open questions and conjectures on the topic.\u00a0\u00a0Essentially, most of the results\u00a0follow from repeated use of orthogonality<\/em>: the fact that a circuit and\u00a0cocircuit of a matroid cannot intersect in a single element.<\/p>\n

To start with, let’s consider matroids where every $t$-element subset of the\u00a0ground set appears in an $\\ell$-element circuit and an $\\ell$-element\u00a0cocircuit; for brevity, call these $(t,\\ell)$-matroids<\/em>.<\/p>\n

For example, wheels and whirls are (1,3)-matroids: every element in a wheel or whirl appears in a triangle (a\u00a03-element circuit) and a triad (a 3-element cocircuit).\u00a0\u00a0Excluding the rank-2 wheel, these matroids are 3-connected, and, due to the\u00a0triangles and triads, deleting or contracting any single element results in a\u00a0matroid that is no longer 3-connected.\u00a0\u00a0Tutte’s Wheels-and-Whirls Theorem states that these are in fact the only\u00a03-connected matroids with no single-element deletion or contraction preserving\u00a03-connectedness.<\/p>\n

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

\n

(2,4)-matroids, a.k.a. spikes<\/h1>\n

So what can we say about (2,4)-matroids? Joel Miller [Miller2014] showed the following:<\/p>\n

Theorem<\/strong>:<\/strong>
\nLet $M$ be a matroid with $|E(M)| \\ge 13$.\u00a0\u00a0Then $M$ is a (2,4)-matroid if and only if $M$ is a spike.<\/p>\n

One way of defining a spike<\/em> (useful for the purposes of this post) is as a\u00a0matroid with a partition into pairs $(X_1,X_2,\\ldots,X_t)$, for some $t \\ge 3$, such\u00a0that for all distinct $i,j \\in [t]$, $X_i \\cup X_j$ is both a circuit and a\u00a0cocircuit.\u00a0\u00a0Note that all “spikes” in this post are what are sometimes referred to as\u00a0tipless spikes.<\/p>\n

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

As I mentioned earlier, since spikes are (2,4)-matroids, they have no pair of\u00a0elements whose deletion or contraction remains 3-connected.\u00a0\u00a0In fact, Alan Williams [Williams2015] showed that the only 3-connected matroids\u00a0having this connectivity property, with $|E(M)| \\ge 13$, and no triangles or\u00a0triads, are spikes.\u00a0\u00a0So in this case, (2,4)-matroids are the only<\/em>\u00a0exceptional matroids appearing\u00a0in a chain theorem for removing a pair of elements from a 3-connected matroid\u00a0with no triangles or triads, and retaining 3-connectivity (the caveat being the “no triangles or triads” condition: I’ll touch more on\u00a0this in the section after next).<\/p>\n

\n

$(t,2t)$-matroids, a.k.a. $t$-spikes<\/h1>\n

With Rutger Campbell, Deborah Chun, Kevin Grace, and Geoff Whittle [BCCGW2018], we\u00a0generalised Miller’s result as follows.<\/p>\n

Theorem:<\/strong>
\nLet $M$ be a matroid, and let $t$ be a positive integer. For each $t$, there exists\u00a0an $n_t$ such that if $M$ is a matroid with the $(t,2t)$-property and $|E(M)| \\ge\u00a0n_t$, then $M$ has a partition into pairs such that the union of any $t$ pairs is\u00a0both a circuit and a cocircuit.<\/p>\n

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

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$.\u00a0 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}$.\u00a0 $t$-spikes share some well-known properties of spikes: A $t$-spike $M$ with $r$ legs has rank $r$ (where a leg<\/em>\u00a0is one of the\u00a0pairs in the partition $\\pi$), and, when $r$ is sufficiently large, $M$ is\u00a0$(2t-1)$-connected.\u00a0 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]).<\/p>\n

A $(t+1)$-spike $M_2$ can be obtained from a $t$-spike $M_1$ (with sufficiently many legs), by the following construction.\u00a0\u00a0Recall that $M_1’$ is an elementary quotient<\/em>\u00a0of $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’$.\u00a0\u00a0First, 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.\u00a0\u00a0Note 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.
\nFor the purposes of this post, I’ll refer to this operation as an inflation<\/em>\u00a0of a $t$-spike.\u00a0\u00a0We showed, in [BCCGW2018], that for $t \\ge 1$, any $(t+1)$-spike with $r$ legs can be\u00a0obtained from a $t$-spike with $r$ legs, by an inflation.<\/p>\n

Spikes are ubiquitous in matroid theory; perhaps $t$-spikes may also be an interesting family of matroids.<\/p>\n

\n

$(t_1,\\ell_1,t_2,\\ell_2)$-matroids<\/h1>\n

Recall that spikes (i.e. (2,4)-matroids) are the only 3-connected\u00a0triangle-and-triad-free matroids with no pair of elements whose deletion or\u00a0contraction preserves 3-connectivity, when we restrict our attention to\u00a0matroids on at least 13 elements.\u00a0\u00a0What if we want to remove the “triangle-and-triad-free” condition; what\u00a0additional structures arise? (*)
\nCertainly wheels and whirls (i.e. (1,3)-matroids) for one, but this is not all.\u00a0\u00a0Another example is any matroid where every pair of elements is in a 4-element\u00a0circuit, and every element is in a triad.<\/p>\n

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

Theorem<\/strong>:<\/strong>
\nFor $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$.<\/p>\n

So $M(K_{3,n})$ and $M^*(K_{3,n})$ are answers to (*). But there are other\u00a0structures 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 (*)).<\/p>\n

Apart from the [OPSW2018] result and the case where $t_1 = t_2$ and\u00a0$\\ell_1 = \\ell_2$, these $(t_1,\\ell_1,t_2,\\ell_2)$-matroids have had little\u00a0attention, as far as I know.\u00a0\u00a0We conjecture the following in [BCCGW2018]:<\/p>\n

Conjecture:<\/strong>
\nAny 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.<\/p>\n

\n

$t$-cyclic matroids<\/h1>\n

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

It seems that obtaining a single-element chain theorem for 4-connectivity in\u00a0the style of Tutte’s Wheels-and-Whirls Theorem has its difficulties (to put it\u00a0lightly) — see, for example, [CMO2011] for internally 4-connected binary\u00a0matroids.<\/p>\n

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

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

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

We say that a matroid has the cyclic $(t-1,t)$-property<\/em> if there is an\u00a0ordering $\\sigma$ of the ground set such that every set of $t-1$ consecutive\u00a0elements in $\\sigma$ is contained in a $t$-element circuit and a $t$-element\u00a0cocircuit.<\/p>\n

So wheels and whirls have the cyclic (2,3)-property.\u00a0\u00a0Note also that swirls and spikes (i.e. 2-spikes) have the (3,4)-cyclic property.\u00a0\u00a0In fact, $t$-spikes have the $(2t-1,2t)$-cyclic property.<\/p>\n

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

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

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

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

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

Conjecture [BCFS2018]:<\/strong>
\nLet M be a $t$-cyclic matroid for some $t \\ge 2$.
\nIf $t$ is even, then M can be obtained from a spike or a swirl by a sequence of\u00a0inflations.
\nIf $t$ is odd, then M can be obtained from a wheel or a whirl by a sequence of\u00a0inflations.<\/p>\n

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

If you’ve made it this far in the post, the reward is a potentially\u00a0foolhardy conjecture or two.<\/p>\n

As touched on earlier, I think perhaps there is some hope for a “nice”\u00a0characterisation of $(1,t)$-matroids for odd $t \\ge 5$.\u00a0\u00a0Here is an optimistic conjecture:<\/p>\n

Conjecture:<\/strong>
\nLet $t$ be an odd integer, with $t \\ge 3$.\u00a0\u00a0There 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.<\/p>\n

In fact, I’m not even aware of sporadic examples.<\/p>\n

Question:<\/strong>
\nFor 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?<\/p>\n

Bibliography:<\/h3>\n

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

At the end of November 2017, the Tutte Centenary Retreat\u00a0was held.\u00a0\u00a032 researchers gathered in Creswick Australia to work on problems in three areas\u00a0where Tutte made seminal contributions. One of those three areas was Matroid\u00a0Structure Theory: nine of us (Rutger Campbell, … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-2394","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2394","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2394"}],"version-history":[{"count":10,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2394\/revisions"}],"predecessor-version":[{"id":2405,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2394\/revisions\/2405"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2394"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2394"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2394"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}