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.

Today we’ll return to our examination of infinite matroids. So far we saw why they are defined the way they are and what the known examples look like. Then we examined a very flexible way of building infinite matroids from trees of finite matroids and saw how to use that construction as a tool in topological infinite graph theory.

The aim today is to understand the deepest and most important unproved conjecture about infinite matroids, the infinite matroid intersection conjecture. We won’t be looking at progress towards the conjecture today, just approaching the statement from a number of angles and getting a sense of its connections to various very different-looking problems in infinite combinatorics. I hope that by the end of the post you will be convinced, as I am, that it is a deep and compelling problem. Here it is:

Conjecture (Nash-Williams): Let $M$ and $N$ be (possibly infinite) matroids on the same ground set $E$. Then there are a subset $I$ of $E$ and a partition of $E$ into sets $P$ and $Q$ such that $I$ is independent in both $M$ and $N$, $I \cap P$ spans $P$ in $M$ and $I \cap Q$ spans $Q$ in $N$.

Like a TARDIS, at a first glance this statement seems simple and perhaps a little odd, and its deeper significance is hidden. To get a sense of that significance, we must go on a long journey and see how it materialises within apparently widely separated worlds.

Our journey begins with the observation that finding good infinite versions of theorems about finite combinatorial objects is hard. All too often, the obvious generalisation is either straightforwardly false or else is a simple consequence of the finite version of the theorem, and as such has no new content.

An example of the latter phenomenon is Menger’s Theorem. If $G$ is a graph and $A$ and $B$ are sets then an $A$-$B$ separator in $G$ is defined to be a set $S$ of vertices of $G$ such that there is no path from $A$ to $B$ in $G – S$. Menger’s theorem states that if $G$ is finite then the minimal size of an $A$-$B$ separator in $G$ is the same as the maximal size of a set of disjoint paths from $A$ to $B$ in $G$.

The obvious way to generalise this statement to infinite graphs would be to simply replace the word ‘size’ with the word ‘cardinality’ in both places where it appears. However, the statement obtained in this way has no more content than the finite version of the theorem. We can see this by considering an $A$-$B$ separator $S$ of minimal cardinality.

If $S$ is infinite, then any set of fewer than $|S|$ paths from $A$ to $B$ uses fewer than $|S|$ vertices, and so cannot be maximal. So in that case the statement is clear, and we can suppose instead that $|S|$ is some natural number $n$. Now for each $m \leq n$ we can easily build a finite subgraph $G_m$ of $G$ in which any $A$-$B$ separator has size at least $m$: we may take $G_0$ to be empty, and build $G_{m+1}$ from $G_m$ by adding a path $P_X$ of $G$ from $A$ to $B$ avoiding each set $X$ of $m$ vertices of $G_m$. Then by Menger’s theorem $G_n$ already contains $n$ disjoint paths from $A$ to $B$.

It was Paul Erdős who saw how to get a much deeper infinite generalisation by first reformulating Menger’s theorem as a structural statement. Suppose that we consider an $A$-$B$ separator $S$ of minimal size and a set $\cal P$ of disjoint paths from $A$ to $B$ of maximal size. Then each path in $\cal P$ contains at least one vertex in $S$, and these vertices must all be distinct since the paths are disjoint. But by Menger’s theorem there can only be as may paths in $\cal P$ as there are vertices in $S$. So $S$ must consist of one vertex on each path in $\cal P$.

So it follows from Menger’s theorem that in a finite graph $G$ we can always find a set $\cal P$ of disjoint $A$-$B$ paths together with an $A$-$B$ separator $S$ consisting of one vertex from each path in $\cal P$. On the other hand, this structural statement also implies Menger’s theorem. After all, if ${\cal P}’$ is a set of disjoint paths from $A$ to $B$ of maximal size and $S’$ is an $A$-$B$ separator of minimal size then $|S’| \leq |S| = |{\cal P}| \leq |{\cal P}’|$. But also $|{\cal P}’| \leq |S’|$ since each path in ${\cal P}’$ must contain a different point of $S’$. So $|{\cal P}’| = |S’|$, as desired.

Erdős’ generalisation of Menger’s theorem is therefore the following structural statement:

Theorem (Aharoni and Berger): Let $G$ be a (possibly infinite) graph and let $A$ and $B$ be sets. Then there is a set ${\cal P}$ of disjoint $A$-$B$ paths together with an $A$-$B$ separator $S$ consisting of one vertex from each path in ${\cal P}$.

This statement contains some serious content about the structure of infinite graphs, and it remained open for almost half a century before finally being proved by Aharoni and Berger in 2009 [AB09]. Their proof remains one of the deepest ever given in infinite combinatorics.

Another example of the difficulties of generalisation from finite to infinite objects is given by the tree packing and covering theorems. The tree covering theorem states that a connected graph $G$ is a union of $k$ spanning trees if and only if for any set $X$ of vertices of $G$ the induced subgraph $G[X]$ has at most $k(|X| – 1)$ edges, and the tree packing theorem states that a connected graph $G$ includes $k$ edge-disjoint spanning trees if and only if for any partition $P$ of the vertex set of $G$, the quotient graph $G/P$ has at least $k(|P|-1)$ edges. Here $G/P$ is the graph whose vertices are the partition classes and whose edges are those of $G$ which go between partition classes, with endpoints the partition classes which they join.

Once more, the obvious generalisation of the tree covering theorem to infinite graphs has no more content than the finite version of the theorem; it can be proved from it by a straightforward compactness argument. On the other hand the obvious generalisation of the tree packing theorem to infinite graphs is false; there is a counterexample due to Aharoni and Thomassen [AT89]. And once more, to find the correct infinite version of the theorems we must begin by finding a structural version in the finite case. Indeed, it turns out that the tree packing and covering theorems have a unifying structural generalisation:

Theorem ([D17, Theorem 2.4.4]): Let $G$ be a connected finite graph and $k$ a natural number. Then there is a partition $P$ of the vertex set of $G$ such that $G/P$ is a union of $k$ spanning trees and $G[X]$ is connected and has $k$ edge-disjoint spanning trees for each partition class $X$ of $P$.

This tree packing/covering theorem implies both the tree packing theorem and the tree covering theorem. For tree packing, the necessity of the condition is clear, so it suffices to prove sufficiency. We can do this by applying the condition to the partition $P$ given by the tree packing/covering theorem. This gives that $G/P$ has at least $k(|P|-1)$ edges. Since it is a union of $k$ spanning trees, those trees must be edge disjoint. Combining these with the edge-disjoint spanning trees in each $G[X]$ gives $k$ edge-disjoint spanning trees in $G$. The derivation of the tree covering theorem from the packing/covering theorem is similar.

This gives us a nontrivial common generalisation of the tree packing and covering theorems to infinite graphs: we can simply omit the word ‘finite’ from the tree packing/covering theorem. The proof of this generalisation, though much simpler than that for the infinite version of Menger’s theorem, goes beyond the scope of this post.

We have now seen two examples where, to find the correct infinite generalisation of a theorem about finite graphs, it was necessary to first reformulate the finite theorem as a structural result. The same is true for theorems about finite matroids, but in this case something remarkable happens. The infinite structural statement you get is usually just the infinite matroid intersection conjecture!

This is not too surprising for the matroid intersection theorem, since Nash-Williams formulated the intersection conjecture to be an infinite structural generalisation of that statement. Recall that the matroid intersection theorem states that the largest size of a common independent set of two matroids $M$ and $N$ on the same ground set $E$ is the same as the minimum value over all partitions of $E$ into sets $P$ and $Q$ of $r_M(P) + r_N(Q)$. The inequality one way around is clear, since if $I$ is independent in both $M$ and $N$ and $\{P, Q\}$ is a partition of $E$ then $|I| = |I \cap P| + |I \cap Q| \leq r_M(P) + r_N(Q)$. For this inequality to be an equality, we must have that $I \cap P$ spans $P$ in $M$ and $I \cap Q$ spans $Q$ in $N$, just as in the conjecture.

There are some less expected cases. Let’s consider Tutte’s linking theorem, the closest matroidal analogue of Menger’s theorem. Let $M$ be a finite matroid with ground set $E$, and let $A$ and $B$ be disjoint subsets of $E$. Let $E’ := E \setminus (A \cup B)$. Then the connectivity $\lambda_M(A, B)$ from $A$ to $B$ in $M$ is defined to be the minimal value of $\kappa_M(A \cup P)$ over all bipartitions of $E’$ into sets $P$ and $Q$. Here $\kappa_M$ is the connectivity function of $M$, given by $\kappa_M(X) := r_M(X) + r_M(E \setminus X) – r(M)$. The linking theorem states that the maximum value of $\kappa_N(A)$ over all minors $N$ of $M$ with ground set $A \cup B$ is $\lambda_M(A,B)$.

It turns out that there is a structural analogue of this statement. Each such minor $N$ must have the form $M/I\backslash J$, where $I$ and $J$ form a partition of $E’$. By moving loops of $M/I$ into $J$ if necessary, we may suppose that $I$ is independent. We may now calculate as follows:

$\kappa_{M/I \setminus J}(A) = (r(A \cup I) – |I|) + (r(B \cup I) – |I|) – (r(M) – |I|) \\= (r(A \cup I) – |Q \cap I|) + (r(B \cup I) – |P \cap I|) – r(M) \\ \leq r(A \cup (I \cap P)) + r(B \cup (I \cap Q)) – r(M)  \\ \leq r(A \cup P) + r(B \cup Q) – r(M) \\ = \kappa_M(A \cup P)$

So equality of the left and right sides is equivalent to the statement that each inequality in the above calculation is an equality, giving the following four conditions:

1. $I \cap P$ spans $P$ in $M/A$
2. $I \cap Q$ spans $Q$ in $M/B$
3. $I \cap P$ is independent in $M/(B \cup (I \cap Q))$
4. $I \cap Q$ is independent in $M/(A \cup (I \cap P))$

The outlines of our TARDIS are beginning to materialise. Indeed, consider a minimal set $I$ satisfying these conditions. By minimality, $I \cap P$ will be independent in $M/A$ and $I \cap Q$ will be independent in $M/B$. Thus $I$ itself will be independent in both matroids. To put it another way, $I$, $P$ and $Q$ will witness that $M/A \backslash B$ and $M \backslash A/B$ satisfy the matroid intersection conjecture.

Thus the infinite generalisation of Tutte’s linking theorem is the statement that, for any (possibly infinite) matroid $M$ and any disjoint sets $A$ and $B$ of elements of $M$, the matroids $M/A\backslash B$ and $M \backslash A/B$ satisfy the infinite matroid intersection conjecture. Given this connection, it should not be too surprising that Aharoni and Berger’s infinite generalisation of Menger’s theorem follows from the infinite matroid intersection conjecture. Precise details of the derivation can be found in [ACF18].

What about the tree packing and covering theorems? Their matroidal analogues are the base packing and covering theorems, which in their full generality apply to a list $M_1, M_2, \ldots M_k$ of finite matroids on a common ground set $E$. A base packing for such a list is a collection of disjoint bases, one from each $M_i$. A base covering for such a list is a collection of bases, one from each $M_i$, whose union is the whole of $E$. The base packing theorem states that there is a base packing precisely when for any subset $Q$ of $E$ we have $\sum_{i = 1}^k r(M_i.Q) \leq |Q|$, and the base covering theorem states that there is a base covering precisely when for any subset $P$ of $E$ we have $\sum_{i = 1}^k r(M_i | P) \geq |P|$.

Once more we can combine these statements into a unified structural statement, the base packing/covering theorem, which states that given such a list of finite matroids on $E$ we can find a bipartition of $E$ into sets $P$ and $Q$ such that the matroids $M_1 | P, \ldots M_k | P$ have a packing and the matroids $M_1.Q, \ldots M_k.Q$ have a covering. The derivations of the base packing and covering theorems from this statement are analogous to the derivation of the tree packing theorem from the tree packing/covering theorem above. So the infinite version of the base packing and covering theorems is given by the same statement applied to a family of infinite matroids. We shall call this the base packing/covering conjecture.

Let’s consider the special case $k = 2$ in more detail. The existence of a packing for $M_1 | P$ and $M_2 | P$ is equivalent to the existence of a subset $I_P$ of $P$ such that $I_P$ spans $P$ in $M_1$ and $P \setminus I_P$ spans $P$ in $M_2$. Similarly the existence of a covering for $M_1.Q$ and $M_2.Q$ is equivalent to the existence of a subset $I_Q$ of $Q$ such that $I_Q$ is independent in $M_1/P$ and $Q \setminus I_Q$ is independent in $M_2/P$. Since a set is independent in a matroid precisely when its complement is spanning in the dual matroid, we can rephrase these conditions as follows:

1. $I_P$ spans $P$ in $M_1$
2. $I_Q$ spans $Q$ in $M_2^*$
3. $I_P$ is independent in $M_2^*/Q$
4. $I_Q$ is independent in $M_1/P$

Once again, as if from nowhere, the TARDIS appears. If we choose $I_P$ and $I_Q$ minimal subject to conditions (i) and (ii) then they will still satisfy conditions (iii) and (iv), which will guarantee that $I:=I_P \cup I_Q$ is independent in both $M_1$ and $M_2^*$, meaning that $I$, $P$ and $Q$ witness that $M_1$ and $M_2^*$ satisfy the infinite matroid intersection conjecture.

The TARDIS not only appears in unexpected places, it is also bigger on the inside than it seems. For example, the remarks in the last couple of paragraphs only apply to pairs of matroids, that is, to lists of length 2. But in fact it is possible to derive the full base packing/covering conjecture from the special case of pairs, and hence from the infinite matroid intersection conjecture. We will see the reasons for this when we look at the structure of the conjecture more closely in the next post in the series. For now we just note the consequence that the tree packing/covering theorem mentioned earlier also follows from the infinite matroid intersection conjecture.

We have seen how the infinite matroid intersection conjecture arises naturally as the infinite structural analogue of the matroid intersection theorem, the linking theorem, and the base packing and covering theorems. The same also holds for the matroid union theorem, which we do not have space to discuss here [BC15]. Thus the process of finding an infinite generalisation of all these statements reveals their unified structural heart. In the next post we will examine that structural heart more closely, looking at just what sort of structure the conjecture gives us, and we will survey the special cases for which the conjecture is already known.

Bibliography:

[AB09] R. Aharoni and E. Berger, Menger’s Theorem for Infinite Graphs, Inventiones mathematicae 176(1):1–62 (2009).

[ACF18] E. Aigner-Horev, J. Carmesin and J.-O. Fröhlich, On the Intersection of Infinite Matroids, Discrete Mathematics 341(6):1582-1596 (2018).

[AT89] R. Aharoni and C. Thomassen, Infinite, highly connected digraphs with no two arc-disjoint spanning trees. J. Graph Theory, 13:71–74 (1989).

[BC15] N. Bowler and J. Carmesin, Matroid Intersection, Base Packing and Base Covering for Infinite Matroids, Combinatorica 35(2):153-180 (2015).

[D17] R. Diestel, Graph Theory, 5th edition, Springer-Verlag (2017).