About Nathan Bowler

I'm working at the university of Hamburg on infinite matroid theory.

Partitioning infinite matroids into circuits

Although this post is part of the ongoing series on infinite matroids, it begins with an old result about graphs. Suppose that you have a graph $G$, and you want to know whether you can partition it into an edge-disjoint union of cycles. If $G$ is finite then there is a straightforward necessary and sufficient condition for this; every vertex of $G$ should have even degree. Necessity is obvious, and to see sufficiency note that as long as $G$ has any edges it cannot be a tree so it must contain some cycle; after deleting the edges of that cycle, every vertex still has even degree and so we can keep doing the same again until we have exhausted all the edges of the graph. 

What if $G$ is infinite? In that case it is no longer sufficient that all degrees are even. Indeed, consider the two-way infinite ray; every vertex has degree 2, but there isn’t even a single cycle. So we need a stronger condition. Rather than considering individual vertices, we should consider cuts. Since any cycle meets any cut in an even number of edges, if $G$ is an edge-disjoint union of cycles then every cut of $G$ must be a disjoint union of finite sets of even size, so must itself be even or infinite. In 1960, Nash-Williams showed that this condition is sufficient [3].

Theorem 1: Let $G$ be any graph. Then $G$ is an edge-disjoint union of cycles if and only if $G$ has no finite cuts of odd size.

In this post we will examine various generalisations of this result, as well as some of the basic ideas used to prove them, and we will finish up by looking at some intriguing open problems which remain. However, we will not look at Nash-Williams’ original proof, since that was long and technical, and over the years more efficient proofs have emerged (see for example [4],[5]).

Roughly speaking, the modern proofs work in the following way. We want to prove the result by induction on the cardinality of $G$. As the base case, we suppose that $G$ is countable. In this case, we can use an argument like the one above to recursively pick a sequence of edge-disjoint cycles $C_1, C_2,\ldots$ covering all edges of $G$.

For the induction step, we want to break $G$ up into strictly smaller edge-disjoint subgraphs of smaller cardinality, which we will use to cover larger and larger chunks of $G$. We will make sure that each of these subgraphs $H$ has the following properties:

  1. Any finite cut of $H$ is also a cut of $G$
  2. Any finite cut of $G – E(H)$ is also a cut of $G$

The first of these properties is obviously useful, since it ensures in particular that $H$ has no finite odd cuts, so that we can apply the induction hypothesis to it. It is also easy to extend any infinite subgraph $X$ of $G$ to a subgraph $H$ of the same cardinality satisfying (1), by repeatedly taking each finite cut of $X$ which isn’t a cut of $G$ and either adding all edges of the corresponding cut of $G$ (if that cut is finite) or infinitely many edges of the corresponding cut of $G$ (if that cut is infinite). So by closing under this operation we can easily extend any subgraph of $G$ to one satisfying (1).

The second property is used in a recursive construction of our partition of $G$ into subgraphs, to ensure that after we have taken $H$ as a partition class we still have no odd-sized cuts in the remainder and so we can continue finding more partition classes in the same way. Rather surprisingly, there is another operation, akin to that in the previous paragraph but more technical, such that by closing under that operation we can turn any subgraph of $G$ into another of the same cardinality satisfying (2). Even more surprisingly, the exact details of that operation need not be specified for the proof. 

Why not? There is a very useful trick, often applicable in such situations, called the Elementary Submodel Method. It allows us to define a kind of universal closure operation, which when applied to a subgraph closes it under almost anything we might have wanted. That seems miraculous. How could it possibly work? The idea is to make use of a result from logic called the Löwenheim-Skolem Theorem, which states that if we have some theory expressed using first-order logic, some model $M$ of that theory and some infinite subset $X$ of $M$ then we can find a submodel $N$ of $M$ including $X$ and of the same cardinality as $X$, such that any first order statement which holds (in $N$) for some elements of $N$ still holds for those same elements in $M$. $N$ is then called an elementary submodel of $M$. 

A first idea about how to apply this might be to take $M$ to be the graph $G$, considered as a model of the theory of graphs, and define $H$ to be the subgraph corresponding to $N$. Then for any construction we can express in the language of graphs, $H$ will be closed as a subgraph of $G$ under that construction. This is already fairly powerful, but unfortunately the operations under which we want to close subgraphs are often too complicated to be expressible using first-order logic in the language of graphs. So we need a more powerful idea.

What we do instead is to take $M$ to be the whole set-theoretic mathematical universe (considered as a model of the axioms of set theory). Given an infinite subgraph $X$ of $G$ we can now find an elementary submodel $N$ of $M$ including $X$ and containing $G$. If we define $H$ to be the intersection of $N$ with $G$ then it will really be closed under any operation we might think of. Any readers who are logicians might now be worried about whether it is really ok to step outside the set-theoretic universe and treat that whole universe as a mathematical object in this way. Would it then be contained in itself? This is a valid worry, but it can be circumvented by instead taking $M$ to be a large enough fragment of the set-theoretic universe, rather than the whole thing. 

For those reading about the Elementary Submodel Method for the first time, I understand that it can be a little mind-blowing the first time you see it. I remember that it took me a while to wrap my head around it. For the purposes of this post, all you need to remember is that it gives you a kind of universal closure operation, which (with a little more work) lets us push through the proof outlined above.

However, if at some point in life you find yourself working with some recursive construction where you would like to close some infinite graphs (or indeed matroids) under some very technical operations, and perhaps it isn’t easy to see exactly what those operations should be, do consider whether the Elementary Submodel Method might be a helpful tool for you. A good introduction can be found in [4].

What we want to focus on for now is how the same method allows us to extend Nash-Williams’ results to infinite matroids. The obvious question to ask is when we can express the ground set of a matroid as a disjoint union of circuits. In the discussion above, we relied on the fact that every cycle in a graph meets every cut in an even number of edges. The corresponding property in the language of matroids would be that every circuit-cocircuit intersection is even, or to put it another way, that the matroids we are working with are binary. And indeed we do get a corresponding result for infinite binary matroids, with a very similar proof:

Theorem 2: Let $M$ be a finitary binary matroid such that no finite cocircuit of $M$ has odd size. Then the ground set of $M$ is a disjoint union of circuits.

Note that this theorem is only for finitary matroids, which means that all circuits are finite, not for infinite matroids in general. We will return to this point later. However, it turns out that the theorem above can be generalised slightly beyond binary matroids. It turns out that what we need to do is to make precise exactly what it is that is used about circuits in binary matroids for the base case of an argument of the kind outlined above. 

Remember that the base case was that in which $M$ is countable. Our plan there was to recursively define a sequence of disjoint circuits $C_1, C_2, \ldots$ covering the ground set. To define $C_n$, we need that even after we have deleted the circuits $C_1, \ldots, C_{n-1}$ there is still at least one more circuit to choose as $C_n$. To ensure that we ultimately cover the whole ground set, we also need that we can choose this new circuit to contain our favourite edge $e$ of $M$. We can formalise all of this as follows:

Definition: A matroid $M$ is finite matching extendable if for any finite list $C_1, \ldots C_{n-1}$ of disjoint circuits of $M$ and any edge $e$ of $M$ not in any $C_i$ there is some circuit $C_n$ of $M$ containing $e$ and disjoint from all the other $C_i$.

So what we are using to prove the base case in our argument for finitary binary matroids is the fact that they are finite matching extendable. Komjáth, Milner and Polat showed [2] that this property also suffices for the general case.

Theorem 3: Let $M$ be any finitary matroid which is finite matching extendable. Then the ground set of $M$ is a disjoint union of circuits.

Once again, Komjáth, Milner and Polat’s proof was tricky and technical. However, using the Elementary Submodel Method, Attila Joó and I were able to give a much shorter alternative proof. 

Instead of generalising Theorem 1 to matroids, a natural question to ask is what happens for directed graphs. More precisely, a natural question to ask in this context is which directed graphs can be expressed as a disjoint union of directed cycles. After a little thought, it is clear that the following statement is the analog of Theorem 1 for directed graphs:

Theorem 4: Let $D$ be any directed graph such that every for every cut $K$ of $D$ the sets of edges crossing $K$ in each direction have the same cardinality. Then $D$ is a disjoint union of directed cycles. 

The history of this statement is a little peculiar. After proving Theorem 1 in 1960, Nash-Williams claimed that his methods could also be extended to give Theorem 4. However, he did not explain how to do so, and over the decades nobody else was able to reconstruct such a proof. Finally, in 2017 Thomassen gave Theorem 4 as a conjecture in [5], and a few years later this conjecture was finally proved by Attila Joó [1] using the Elementary Submodel Method.

Since we could generalise Theorem 1 to matroids, it is natural to ask whether we can also generalise Theorem 4 to matroids. And indeed we can, namely to regular matroids. To understand the statement, we need to understand what the analog of a directed cycle in a regular matroid might be. A quick way to express the concept we need is by using an alternative characterisation of regular matroids due to White [6].

Definition: A signing of a matroid $M$ consists of a choice, for each circuit $C$ of $M$, of a function $f_C \colon C \to \{-1, 1\}$ and a choice, for each cocircuit $D$ of $M$, of a function $g_D \colon D \to \{-1, 1\}$, such that for any circuit $C$ and cocircuit $D$ we have $$\sum_{e \in C \cap D} f_C(e)g_D(e) = 0\,.$$ A signed matroid is a matroid together with a signing of that matroid.

Fact: A matroid $M$ is regular if and only if it has a signing.

For example we can find a signing of the matroid associated to any graph $G$ by directing the edges of $G$ arbitrarily, defining each $f_C$ to be 1 on the edges directed in one sense around $C$ and -1 for the edges directed in the opposite sense, and defining each $g_D$ to be 1 on the edges crosssing $D$ in one direction and -1 on the edges crossing $D$ in the opposite direction. The desired equation holds since each cycle crosses each cut the same number of times in each direction.

In this context, it is clear what the analog of a directed cycle should be. We say that a circuit $C$ (or cocircuit $D$) of a signed matroid is directed if $f_C$ (or $g_D$) is constant. Attila and I were able to extend Theorem 4 to regular matroids as follows:

Theorem 5: Let $M$ be a finitary signed matroid such that for any cocircuit $D$ of $M$ the sets $g_D^{-1}(-1)$ and $g_D^{-1}(1)$ have the same cardinality. Then the ground set of $M$ is a disjoint union of directed circuits. 

All of the matroidal statements we have considered here were for finitary matroids. The reason for this, however, is not that they are known to be false for infinitary matroids. Indeed, there are no known counterexamples even for general infinite matroids. I would be very interested in any ideas for how to prove or refute the corresponding statements for arbitrary infinite matroids.

However there is an even more basic statement from which the countable case of Theorem 5 quickly follows, which is also open for general infinite matroids. It is an analog of the Farkas Lemma for signed matroids. It would probably be needed for any proof of Theorem 5 for general infinite matroids. So I would be extremely interested in any ideas on how to approach this problem.

Conjecture: Let $M$ be a (possibly infinite) signed matroid and $e$ an edge of $M$. Then $e$ is either contained in a directed circuit or a directed cocircuit. 

References:

[1] Attila Joó. “On partitioning the edges of an infinite digraph into directed cycles”. In: Advances in Combinatorics 2.8 (2021)
[2] Péter Komjáth, Eric Charles Milner, and Norbert Polat. “A compactness theorem for perfect matchings in matroids”. In: Journal of Combinatorial Theory, Series B 44.3 (1988), pp. 253–262.
[3] C. St. J. A. Nash-Williams. “Decomposition of graphs into closed and endless chains”. In: Proceedings of the London Mathematical Society 3.1 (1960), pp. 221–238.
[4] Lajos Soukup. “Elementary submodels in infinite combinatorics”. In: Discrete Math- ematics 311.15 (2011), pp. 1585–1598.
[5] Carsten Thomassen. “Nash-Williams’ cycle-decomposition theorem”. In: Combina- torica 37.5 (2017), pp. 1027–1037.
[6] Neil White. Matroid applications. 40. Cambridge University Press, 1992.

Representing infinite matroids over fields

Looking back over the series of all posts so far on infinite matroids, you might notice (as I did) that there is a central theme which has not yet been covered: that of representability. What should it mean for an infinite matroid to be representable over a field $k$? In this post we will explore a few ideas for how one could try to define this. It will be a fraught journey, with some false starts and paths that get lost in rocky ground, but eventually we will arrive at a satisfying definition.

The obvious thing to try is to just define representability of infinite matroids the same way we define it for finite matroids: take a set $E$ of vectors in some vector space $V$ over $k$, and say that a subset of $E$ is independent if it is linearly independent in $V$. If $E$ is infinite then we have an infinite matroid, and such matroids should certainly count as representable over $k$.

Unfortunately this definition doesn’t cover all the examples of matroids which ought to be representable. For example, in this post we saw a bunch of examples that look like infinite graphic matroids, and graphic matroids should be representable over every field. But these examples are not covered by the definition above. Nor are the examples from this post. Why not? A set of vectors is linearly independent as soon as all of its finite subsets are, so all the circuits of these matroids will necessarily be finite. In other words, all these matroids are finitary.

This might remind of you of the issues which got this whole series of posts started, here and here. It is easy to find axioms for the collection of finitary infinite matroids, but that doesn’t include all the examples of things that look like infinite matroids, and in particular the collection of finitary matroids is not closed under duality. Finding natural axioms for a class of infinite matroids closed under duality was a much trickier problem. Now we are running into exactly the same problem with representability. Not only have we failed to cover the important examples, this definition of representability is not even closed under duality.

Still, we have made some progress. We have identified which finitary matroids should count as representable over $k$, and so whatever our definition turns out to be it should give this collection of matroids as the finitary representable matroids. Since cofinitary matroids are just the duals of finitary matroids, we have also identified which cofinitary matroids should count as representable over $k$, namely the duals of these finitary representable matroids. Taking the union of these two classes would give a class of matroids closed under duality, but this is pretty crude and still doesn’t cover some of the interesting examples.

We need a way to allow infinite linear combinations of our vectors. One natural idea, which quickly turns out to be a dead end, is to use the infinite sums defined in Hilbert spaces (the notion of independence given this way does not give rise to a matroid). A more fertile approach was found by Bruhn and Georgakopoulos [4]. You can understand the basic idea by considering the following list of vectors in $\mathbb{R}^{\mathbb{N}}$:

$$\begin{array}{rrrrrrrrr}(&1,&0,&0,&0,&0,&0,&\ldots&)\\(&-1,&1,&0,&0,&0,&0,&\ldots&)\\(&0,&-1,&1,&0,&0,&0,&\ldots&)\\(&0,&0,&-1,&1,&0,&0,&\ldots&)\\(&0,&0,&0,&-1,&1,&0,&\ldots&)\\&&&\vdots&&&&&\end{array}$$

Although this list is infinite, if we pick any particular column and take the sum of the entries in that column it evaluates to 0. So there is a sense in which this infinite list of vectors sums to 0. More precisely, given a set $I$, we can consider the vector space $k^I$ of functions from $I$ to $k$. Then we say that a set $U$ of vectors in $k^I$ is thinly dependent if we can find coefficients $\lambda_u \in k$ for each $u \in U$, not all zero, such that for any $i \in I$ we have $$\sum_{u \in U} \lambda_u u(i) = 0\,.$$ There is of course the problem that some of these sums might not be defined, in that they might have infinitely many nonzero summands. We say that $U$ is thin if such sums are necessarily well-defined, that is, if for each $i \in I$ there are only finitely many $u \in U$ with $u(i) \neq 0$.

This suggests a new idea for how to define representable matroids. We take the ground set $E$ to be a thin set of vectors in $k^I$, and as dependent sets we take the thinly dependent subsets of $E$. The matroids we get this way need not be finitary, but now we have some new problems. A typical set of vectors in $k^I$ will not be thin, so it isn’t clear that all of the finitary representable matroids we saw above can be presented in this way. And in fact they cannot! Together with Afzali, I showed in [1] that all such matroids are cofinitary, and in fact they are exactly the duals of the finitary representable matroids.

So now we understand representability for finitary and for cofinitary matroids. To make any more progress we need to find a way to squeeze more juice out of the idea of thin dependency. The reason we took $E$ to be a thin family above was to ensure that thin dependency would always be defined for subsets of $E$, but we could drop that requirement if we take more care in our notion of dependency. More precisely, we take as our ground set $E$ any set of vectors in $k^I$, and we say that a subset $X$ of $E$ is dependent if it has a subset $Y$ which is thinly dependent (here $Y$ must be thin, even if $X$ need not be). Matroids arising in this way are called thin sums matroids.

This now includes all the cofinitary representable matroids, and it also includes all the finitary representable matroids (that’s less obvious, but it was shown in [1]). What’s more, it includes all the examples of things we wanted to be representable matroids. But there are some new problems. The systems of dependent sets defined in this way are not always matroids [1]. Even if they are matroids, their duals are not always thin sums representable [2]. Closure under duality is one of the main things we should hope for from a definition of representability. It seems we have hit a dead end.

However, there is a way forward. All of the examples that we cared about, and wanted to cover with our definition of representable matroids, had the property that they were tame, meaning that any intersection of a circuit with a cocircuit is finite. On the other hand, the bad examples where duality breaks down are not tame, but wild. This distinction was already discussed in an earlier post of the series. So we should restrict our attention to tame matroids.

And there we have it: we say that a matroid is representable over $k$ if it is tame and is a thin sums matroid over $k$. Suddenly, magically, everything works. This class is closed under duality [1]. All of the motivating examples are covered. Even better, all the usual theory of representable matroids can be extended to infinite representable matroids. For example, the various standard characterisations of binary and ternary matroids still work in this setting, including the characterisations via excluded minors [3].

Indeed, there is a very general principle which allows the lifting of excluded minor characterisations from finite to infinite matroids. For any finite field $k$, a tame infinite matroid $M$ is representable over $k$ precisely when all of its finite minors are [3]. This principle allows us to lift all kinds of other statements easily from finite to infinite matroids. For example, an infinite matroid which is representable over both $GF(3)$ and $GF(5)$ is necessarily representable over $GF(p)$ for all primes $p$ (since all its finite minors are). 

For those readers who have come across partial fields and tracts, that last statement might have got you wondering whether we can define representations of infinite matroids over those objects, in the spirit of this post. For example, what might it mean for an infinite matroid to be orientable? This is a thorny problem, which will have to wait for a future post.

Although we now have a good definition of representability, there is one open problem in this area that has been nagging at me for years. Binary matroids can be defined as tame matroids with no $U_{2,4}$-minor. But do we really need to impose the condition of tameness here? To put it another way, must every wild matroid have a $U_{2,4}$-minor? All the examples we know of do.

[1] S. Hadi Afzali Borujeni and Nathan Bowler, Thin sums matroids and duality, Advances in Mathematics, Volume 271, 2015, Pages 1-29.
[2] Nathan Bowler and Johannes Carmesin, Matroids with an infinite circuit–cocircuit intersection, Journal of Combinatorial Theory, Series B, Volume 107, 2014, Pages 78-91.
[3] Nathan Bowler and Johannes Carmesin, An excluded minors method for infinite matroids, Journal of Combinatorial Theory, Series B, Volume 128, 2018, Pages 104-113
[4] Henning Bruhn and Agelos Georgakopoulos, Bases and closures under infinite sums, Linear Algebra and its Applications, Volume 435, Issue 8, 2011, Pages 2007-2018.

A breakthrough on the matroid intersection conjecture

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

The infinite matroid intersection conjecture

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