Welcome to the next post in the series on infinite matroids, where I am excited to report some recent progress by Attila Joó on the matroid intersection conjecture. Before that, let’s take some time to get familiar with the conjecture itself. It pops up all over the place in infinite matroid theory. More precisely, there are a number of central theorems of finite matroid theory stating that certain natural bounds on the sizes of sets are tight. In generalising these to infinite matroids, it is often helpful to focus on the combinatorial structures which witness the tightness of the bound. The statement that such structures exist in the infinite case almost always turns out to be a facet of the matroid intersection conjecture. A full explanation would be too long to fit in this post, but luckily it was the subject of the previous post in this series, so please look there if you are interested in more details.

So what does the conjecture say? Let’s say that a pair $(M,N)$ of matroids on the same ground set $E$ has the intersection property if there are a partition of $E$ as $P \cup Q$ and a subset $I$ of $E$, independent in both $M$ and $N$, such that $I \cap P$ is spanning in $M$ and $I \cap Q$ is spanning in $N$. This is exactly the kind of combinatorial structure which would witness the tightness of the bound in the matroid intersection theorem if $M$ and $N$ were both finite. The matroid intersection conjecture states that any such pair $(M,N)$ has the intersection property.

We saw in the previous post that there is a close link between this conjecture and packings and coverings of families of matroids. Recall that a base packing of a family $(M_k)_{k \in K}$ of matroids on the same ground set $E$ consists of a family $(S_k)_{k \in K}$ of bases in the respective matroids, all disjoint from each other, whereas a base covering of such a family consists of a family $(I_k)_{k \in K}$ of bases in the respective matroids whose union is the whole ground set $E$. Finally, we say that such a family of matroids has the packing/covering property if we can partition $E$ as $P \dot \cup Q$ into a packable part $P$ and a coverable part $Q$, such that $(M_k | P)_{k \in K}$ has a base packing and $(M_k.Q)_{k \in K}$ has a base covering. 

The relation of this to intersection is that $(M,N)$ has the intersection property if and only if $(M,N^*)$ has the packing/covering property. Thus by simply dualising one of the matroids we see that it follows from the matroid intersection conjecture that any pair of matroids has the packing/covering property. The packing/covering conjecture is that any family at all of matroids has the packing/covering property.

Although this seems like a far-reaching generalisation, in fact it is already encompassed by the original intersection conjecture. To see why, we have to closely examine a construction which allows us to encode packings and coverings for a family $(M_k)_{k \in K}$ of matroids in terms of packings and coverings for a carefully chosen pair of matroids, namely the direct sum $M := \bigoplus_{k \in K} M_k$ of all the matroids in the family and a direct sum $N := \bigoplus_{e \in E} U_{1,K}^*$ of circuits of size $|K|$, one for each element of the ground set $E$.

Note that both these matroids have the same ground set $K \times E$. We can think of the elements of $K \times E$ as being laid out in a big grid, with the rows indexed by elements of $E$ and the columns by elements of $K$. So $M$ is obtained by putting a copy of $M_k$ in the $k$th column for each $k$, whereas $N$ is obtained by making each row into a circuit. 

What do packings for this pair of matroids look like? Such a packing must consist of bases $S_1$ and $S_2$ in the respective matroids. Let’s think about $S_2$ first, since the structure of $N$ is a little simpler. It must consist of a basis of each row, and since each row is just a circuit, $S_2$ must contain all but precisely one element of each row. On the other hand, $S_1$ consists of a base $S_k$ in each column of the corresponding matroid $M_k$. Since $S_1$ and $S_2$ have to be disjoint, $S_1$ can contain at most one element from each row. That precisely means that the $S_k$ form a base packing for the $M_k$.

The story for coverings is similar. Any covering for $(M,N)$ must consist of bases $I_1$ and $I_2$ in the respective matroids. Once more $I_2$ must contain all but precisely one element of each row. Since the union of $I_1$ and $I_2$ must be the whole ground set, this enforces that $I_1$ must have at least one element in each row, meaning that the bases $I_k$ form a base covering for the $M_k$.

Combining these ideas, we can see that everything works in the same way for the packing/covering property as well. First of all, if we have a partition of $E$ as $P \dot \cup Q$ witnessing the packing/covering property for the $M_k$ then the arguments above show that $\hat P := K \times P$ and $\hat Q = K \times Q$ give a partition of $K \times E$ witnessing the packing/covering property there too. 

The opposite direction seems a little trickier; given a partition of $K \times E$ into sets $\hat P$ and $\hat Q$ witnessing the packing/covering property for $M$ and $N$, there is no reason why $\hat P$ and $\hat Q$ should have the form $K \times P$ and $K \times Q$ for a partition of $P$ and $Q$: there could easily be some row $R$ which meets both $\hat P$ and $\hat Q$. But note that for any such row, the restriction of $N$ to $R \cap \hat P$ is independent, and so in the packing $(S_1, S_2)$ of $(M | \hat P, N | \hat P)$ we have $R \cap \hat P \subseteq S_2$, and so $S_1$ is disjoint from $R$. 

This suggests that we should shift all such rows completely into the $Q$-side of the partition. More formally, we let $P$ be the set of all $e \in E$ whose corresponding row is completely included in $\hat P$. By the above argument we get a packing of $M | (K \times P)$ and $N | (K \times P)$, and so a packing of $(M_k | P)_{k \in K}$. Let $Q$ be the complement of $P$ in $E$: the set of all $e \in E$ whose corresponding row meets $\hat Q$. In the covering $(I_1, I_2)$ of $(M.\hat Q, N.\hat Q)$, it is still true that $I_2$ is missing at least one element from each row meeting $\hat Q$ and so we also get a covering of $(M_k.Q)_{k \in K}$ as above. 

In summary, we see that the family $(M_k)_{k \in K}$ has the packing/covering property if and only if the pair $(M,N)$ does. Hence the packing/covering conjecture for arbitrary families of matroids is equivalent to the packing/covering conjecture for pairs of matroids. Both of these statments, as well as the matroid intersection conjecture, can be seen as different points of view on the same problem. The reductions sketched so far were worked out a while ago by Johannes Carmesin and myself in [1].

Now let’s turn our attention to the progress which has been made so far towards proving the intersection and packing/covering conjectures. More precisely, let’s consider for which special cases the intersection property or the packing/covering property have been proved to hold. Since almost nothing is known in the case that the matroids are uncountable, in the following discussion we will only consider countable matroids. So from now on you can assume that the common ground set of any family of matroids we consider is countable. 

There are two main types of matroid for which the packing/covering conjecture is known. The first deals with matroids built up by gluing together a tree of finite matroids, according to a recipe outlined in a previous post in this series. Together with Johannes Carmesin, I was able to show [2] that any two matroids built according to this recipe along the same tree structure will have the packing/covering property. Since duality is preserved by this construction, and $(M,N)$ has the intersection property precisely when $(M,N^*)$ has the packing/covering property, it follows that any two such matroids also have the intersection property.

The second is the situation in which the matroids are close to being finitary or cofinitary. The first progress in this direction was by Aharoni and Ziv [3], who showed that $M$ and $N$ have the matroid intersection property whenever $M$ is finitary and $N$ is a countable direct sum of matroids of finite rank. Translating in the usual way by dualising $N$, we see that $M$ and $N$ have the packing/covering property whenever $M$ is finitary and $N$ is a countable direct sum of matroids of finite co-rank. 

Using the ideas above, we can derive a much more general result from this one. Suppose that we have any family $(M_k)_{k \in K}$ of finitary matroids, from which we build matroids $M := \bigoplus_{k \in K} M_k$ and $N := \bigoplus_{e \in E} U_{1,K}^*$ as above. Then $M$ will still be finitary, and by definition $N$ will be a sum of a countable family of circuits, which have finite co-rank. By Aharoni and Ziv’s result, $M$ and $N$ has the packing/covering property, and hence so does the family $(M_k)_{k \in K}$. So any family of finitary matroids has the packing/covering property!

We can use similar tricks to obtain the same result for families of cofinitary matroids. We begin again with Aharoni and Ziv’s result, but this time we begin by dualising the other matroid. This tells us that $M$ and $N$ have the packing/covering property whenever $M$ is cofinitary and $N$ is a countable direct sum of matroids of finite rank. If we set $M := \bigoplus_{k \in K} M_k$ and $N := \bigoplus_{e \in E} U_{1,K}^*$ as above, with $(M_k)_{k \in K}$ now a family of cofinitary matroids, then $M$ will certainly be cofinitary, but the circuits $U_{1,K}^*$ will only be of finite rank if $K$ is finite. So it seems that we only obtain that any finite family of cofinitary matroids has the packing/covering property.

But we can press on further. In particular, we now know that any pair $(M,N)$ of cofinitary matroids will have the packing/covering property. If $M$ and $N$ are given as usual by $\bigoplus_{k \in K} M_k$ and $\bigoplus_{e \in E} U_{1,K}^*$, where $(M_k)_{k \in K}$ is an arbitrary family of cofinitary matroids, then both $M$ and $N$ will be cofinitary, so this pair will have the packing/covering property. Thus by bootstrapping in this way we obtain that any family of cofinitary matroids has the packing/covering property.

Using the fact that $(M,N)$ has the intersection property precisely when $(M,N^*)$ has the packing/covering property, either of these two results can be used to obtain the unsatisyfingly asymmetrical statement that any pair consisting of a finitary and a cofinitary matroid has the intersection property. 

This was essentially the state of the art until recently, although together with Johannes Carmesin, Shadisadat Ghaderi and Jerzy Wojciechowski I had developed a technique [4] to extend these results slightly: to matroids which are not quite finitary or cofinitary, but are very close. Thus any family of so-called nearly finitary matroids and any family of nearly cofinitary matroids has the packing/covering property. Any pair consisting of a nearly finitary and a nearly cofinitary matroid has the intersection property.

Recently, however, there has been a remarkable breakthrough: Let’s say that a matroid is simple if all of its components are finitary or cofinitary. Attila Joó has shown [5] that any pair of (countable) simple matroids has the intersection property. Although this may seem similar to the results listed above, it is considerably stronger.

First of all, dualising in the usual way, we can see that it implies that if any pair of simple matroids also has the packing/covering property. Building $M$ and $N$ in the usual way from a family of simple matroids, it follows that any family of simple matroids has the packing/covering property.  

In particular, Attila’s result implies the results from earlier that any family of finitary matroids or of cofinitary matroids has the packing/covering property. But its true depth is made clear from the fact that (still in the countable setting) it implies Aharoni and Berger’s deep and far-reaching generalisation of Menger’s theorem for undirected graphs, as explained in the previous post in this series.

There are still a number of questions in this area where we can hope for future progress. Most pressing is the question of whether Attila’s result can be extended to uncountable matroids. More ambitiously, there remains the question of whether the restrictions of finitariness or cofinitariness can be substantially loosened, or even entirely dropped.

[1] Bowler, N., & Carmesin, J. (2015). Matroid intersection, base packing and base covering for infinite matroids. Combinatorica, 35, 153-180.
[2] Bowler, N. & Carmesin, J. (2021+). On the intersection conjecture for infinite trees of matroids, preprint available at https://arxiv.org/abs/1404.6067
[3] Aharoni, R., & Ziv, R. (1998). The intersection of two infinite matroids. Journal of the London Mathematical Society, 58(3), 513-525. 
[4] Bowler N, Carmesin J, Wojciechowski J, Ghaderi S. (2020). The Almost Intersection Property for Pairs of Matroids on Common Groundset. The Electronic Journal of Combinatorics. 2020,Jul 10:P3-5.
[5] Joó, A. (2021+).On the packing/covering conjecture of infinite matroids, preprint available at https://arxiv.org/abs/2103.14881