On a Cantor-Bernstein property of infinite matroids

Guest post by Attila Joó.

In this post we report an interesting property of infinite matroids that provides a common generalisation of the papers ‘A Cantor-Bernstein theorem for paths in graphs’ by Diestel and Thomassen [1] and ‘A Cantor-Bernstein-type theorem for spanning trees in infinite graphs’ by Erde, Gollin, Joó, Knappe, and Pitz [2]. This generalisation also leads to some new applications.

Let us reformulate the Cantor-Bernstein theorem in the language of graph theory:

Theorem (Cantor-Bernstein [3]): If $ G=(V_0,V_1;E) $ is a bipartite graph and matching $ I_i $ covers $ V_i $ for $ i\in \{ 0,1 \} $, then $ G $ admits a perfect matching.

Ore discovered the following generalisation of the Cantor-Bernstein theorem which is the extension of the Mendelsohn-Dulmage theorem to infinite graphs:

Theorem (Ore [4]): Let $ G=(V_0,V_1;E) $ be a bipartite graph and let $ I_0, I_1\subseteq E $ be matchings in $ G $. Then there exists a matching $ I $ such that $ V(I)\cap V_i\supseteq V(I_i)\cap V_i $ for $ i\in \{ 0,1 \} $.

Diestel and Thomassen [1] examined a more general graph theoretic setting in which disjoint paths are used to connect two vertex sets:

Theorem (Diestel and Thomassen [1]): Assume that $ G=(V,E) $ is a graph, $ V_0, V_1\subseteq V$ and $ \mathcal{P}_i $ is a system of disjoint $V_0V_1$-paths in $ G $ for $ i\in \{ 0,1 \} $. Then there exists a system of disjoint $ V_0V_1 $-paths $ \mathcal{P} $ with $ V(\mathcal{P})\cap V_i \supseteq V(\mathcal{P}_i)\cap V_i $ for $ i\in \{ 0,1 \} $.

In our paper [2] entitled ‘A Cantor-Bernstein-type theorem for spanning trees in infinite graphs’ we investigated if the existence of a $ \kappa $-packing and a $ \kappa $-covering by spanning trees implies the existence of a $ \kappa $-family of spanning trees which is both, i.e. a $ \kappa $-partition:

Theorem (Erde et al. [2]): Let $ G=(V,E) $ be a graph and let $ \kappa $ be a cardinal. If there are $ \kappa $ many pairwise edge-disjoint spanning trees in $ G $ and $ E $ can be covered by $ \kappa $ many spanning trees, then $ E $ can be partitioned into $ \kappa $ many spanning trees.

We believed that the connection between the two previous theorems above is only analogical but it turned out that the connection is actually stronger. Namely, both of them are special cases of a “Cantor-Bernstein theorem” of infinite matroids. To state this matroidal generalisation we fix some notation. We call a matroid (co)finitary if all of its (co)circuits are finite. Note that the cofinitary matroids are exactly the duals of the finitary ones. Let us denote the class of finitary and cofinitary matroids by $ \mathfrak{F} $ and $\mathfrak{F}^{*} $ respectively. Let $ \mathfrak{F}\oplus \mathfrak{F}^{*} $ be the class of matroids having only finitary and cofinitary components, equivalently that are the direct sums of a finitary and a cofinitary matroid (Bowler called them ‘simple matroids’ in the previous post). For a matroid class $ \mathfrak{C} $, let $ \mathfrak{C}(E) $ denote the set of matroids on edge set $ E $ that are in class $\mathfrak{C} $.

Theorem (J.): For $ i\in \{ 0,1 \} $, let $ M_i\in (\mathfrak{F}\oplus \mathfrak{F}^{*})(E) $ and $ F_i\subseteq E $. Then there exists an $ F\subseteq E $ such that $ \mathsf{span}_{M_i}(F)\supseteq F_i $ and $ \mathsf{span}_{M_i^{*}}(E\setminus F)\supseteq E\setminus F_{1-i} $ for $ i\in \{ 0,1 \} $.

The special case where $F_i$ are common independent sets and the matroids are finite is a theorem of Kundu and Lawler [5]. It is worth to mention that $\mathfrak{F}\oplus\mathfrak{F}^{*}$ cannot be replaced by the class of all matroids in the theorem above because the resulting statement fails under the Continuum Hypothesis. We do not know at this point if a counterexample can be found in set theory ZFC alone. It is also unclear if $\mathfrak{F}\oplus\mathfrak{F}^{*}$ can be replaced by some larger “well-behaved” class of matroids like the so called tame matroids. The latter class consists of those matroids in which the intersection of a circuit and a cocircuit is always finite. This class was intensively studied by Bowler, Carmesin and others. It was shown for example by Carmesin that the bases of a fixed tame matroid have the same size. The analogous statement for arbitrary matroids is independent of ZFC (the positive and negative direction of the independence was proved by Higgs and Bowler & Geschke [6] respectively).

In order to derive the mentioned theorem of Diestel and Thomassen [1] from the theorem above, one needs to choose $M_i$ to be the cycle matroid of the graph obtained by contracting $V_{1-i}$ in $G$ and let $F_i:= E(\mathcal{P}_{i})$. One can show that the set of all the $V_0V_1$-paths in $G[F]$ is suitable as $ \mathcal{P}.$ For the spanning tree partitioning result we need a “packing-covering-partitioning family version” of the previous theorem:

Theorem(J.): For $ i\in \Theta$, let $ M_i\in (\mathfrak{F}\oplus \mathfrak{F}^{*})(E) $ and $ P_i,R_i \subseteq E $ such that $ P_i\cap P_j=\varnothing $ for $ i\neq j$ and $ \bigcup_{i\in \Theta}R_i=E $. Then there are $ T_i\subseteq P_i\cup R_i $ for $ i\in \Theta $ forming a partition of $ E $ such that $ \mathsf{span}_{M_i}(T_i)\supseteq P_i $ and $\mathsf{span}_{M_i^{*}}(E\setminus T_i)\supseteq E\setminus R_i $.

This version can be obtained from the previous form in the same way as the Matroid Intersection Conjecture and the Packing-Covering Conjecture can be derived from each other (see the previous post by Bowler). The special case where $P_i$ and $R_i$ are assumed to be bases of $M_i$ is an earlier theorem by Erde et al. [7] and was conjectured by Bowler. By choosing all $M_i$ to be the cycle matroid of $G$, sets $P_i$ to be the (edge sets of) spanning trees forming a packing and the $R_i$ to be spanning trees forming a covering, the sets $T_i$ form the desired partition.

Finally, we mention two applications. According to an unpublished result of Bowler and Carmesin, for every compact graph-like space (introduced by Thomassen and Vella [8]) the edge sets corresponding to pseudo-cycles are the circuits of a cofinitary matroid. This makes it possible to extend the scope of the mentioned theorem of Diestel and Thomassen to compact graph-like spaces (using pseudo-arcs as a replacement of graph theoretic paths).

The other application corresponds to the Matroid Intersection Conjecture of Nash-Williams (discussed in the previous post by Bowler). Let $M_0, M_1 \in (\mathfrak{F}\oplus \mathfrak{F}^{*})(E) $ be fixed. For an $I\in \mathcal{I}_{M_0}\cap \mathcal{I}_{M_1} $ the following statements are known to be equivalent:

1. There is a partition $ E=E_0\sqcup E_1 $ such that $ I_i:=I\cap E_i $ spans $E_i $ in $M_i $ for $ i\in \{ 0,1 \} $.
2. $I$ is strongly maximal, i.e. $ \left|J\setminus I\right|\leq \left|I\setminus J\right| $ for every $ J\in \mathcal{I}_{M_0}\cap \mathcal{I}_{M_1} $.

If the matroids are finite (i.e. $E$ is finite), then ‘strongly maximal’ is equivalent with ‘of maximal size’ but in general strong maximality is a strictly stronger notion. The Matroid Intersection Conjecture claims the existence of a strongly maximal common independent set and is known to be true if $E$ is countable [11].

For $I, J \in \mathcal{I}_{M_0}\cap \mathcal{I}_{M_1} $ let $ J\trianglelefteq I $ iff $ J\subseteq \mathsf{span}_{M_0}(I)\cap \mathsf{span}_{M_1}(I) $. It is not too hard to see that if $E$ is finite, then the strongly maximal (i.e. maximal sized) common independent sets are exactly the $\trianglelefteq $-maximal ones ($I$ is $\trianglelefteq $-maximal iff $ I \trianglelefteq J $ implies $ J \trianglelefteq I $ for every $J\in \mathcal{I}_{M_0}\cap \mathcal{I}_{M_1} $). According to the second application, if $E$ is countable, then the set of the strongly maximal elements of $\mathcal{I}_{M_0}\cap \mathcal{I}_{M_1}$ is $\trianglelefteq $-cofinal in $\mathcal{I}_{M_0}\cap \mathcal{I}_{M_1}$, however, in contrast of the finite case it might be not even upward $\trianglelefteq $-closed in $\mathcal{I}_{M_0}\cap \mathcal{I}_{M_1}$.

[1] R. Diestel and C. Thomassen, A Cantor-Bernstein theorem for paths in graphs, The American Mathematical Monthly 113 (2006), no. 2, 161–166.
[2] J. Erde, J P. Gollin, A. Joó, P. Knappe, and M. Pitz, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs, Journal of Combinatorial Theory, Series B 149 (2021), 16–22.
[3] G. Cantor, Mitteilungen zur lehre vom transfiniten, Zeitschrift für Philosophie und philosophische Kritik 91 (1987), 81–125.
[4] O. Ore, The theory of graphs, American Mathematical Society, 1962.
[5] S. Kundu and E. L Lawler, A matroid generalization of a theorem of Mendelsohn and Dulmage, Discrete Mathematics 4 (1973), no. 2, 159–163.
[6] N. Bowler and S. Geschke, Self-dual uniform matroids on infinite sets, Proceedings of the American Mathematical Society 144 (2016), no. 2, 459–471.
[7] J. Erde, J. P. Gollin, A. Joó, P. Knappe, and M. Pitz, Base partition for mixed families of finitary and cofinitary matroids, Combinatorica 41 (2021), no. 1, 31–52.
[8] C. Thomassen and A. Vella, Graph-like continua, augmenting arcs, and Menger’s theorem, Combinatorica 28 (2008), no. 5, 595–623.
[9] R. Aharoni and R. Ziv, The intersection of two infinite matroids, Journal of the London Mathematical Society 58 (1998), no. 03, 513–525.
[10] A. Joó, Proof of Nash-Williams’ intersection conjecture for countable matroids, Advances in Mathematics 380 (2021), 107608.
[11] A. Joó, On the Packing/Covering Conjecture of infinite matroids (2021). https://arxiv.org/abs/2103.14881
[12] N. Bowler, Infinite matroids, Habilitation Thesis, 2014. https://www.math.uni-hamburg.de/spag/dm/papers/Bowler_Habil.pdf
[13] A. Joó, On a linking property of infinite matroids (2021). https://arxiv.org/abs/2009.08439.

Online Talk: Tara Fife

Tuesday, Oct 19, 3pm ET (8pm BST, 8am Wed NZST)
Tara Fife, Queen Mary University of London
(Minimal) Tropical Basis for Matroids

Password: email shaylaredlin ~at~ gmail ~.~ com (The password is the same format as usual, but first instead of last.)
Counterintuitively, a tropical basis for a matroid is not a type of basis or even a collection of basis. Rather it is a type of subset of the circuit set of a matroid which uniquely determines the matroid. In this talk, we will start by introducing a purely combinatorial definition of (minimal) tropical basis for matroids. We will explore how this definition is equivalent to the standard (algebraic) definition of tropical basis for matroids, and we will discuss some preliminary results. No advanced algebra background is assumed. This is joint work with Yelena Mandelshtam.

Online Talk: Jagdeep Singh

Tuesday, Oct 5, 3pm ET (8pm BST, 8am Wed NZST)
Jagdeep Singh, Louisiana State University
$2$-Cographs and Binary Comatroids

The well-known class of cographs or complement-reducible graphs is the class of graphs that can be generated from $K_1$ using the operations of disjoint union and complementation. In this talk, we consider $2$-cographs, a natural generalization of cographs, and binary comatroids, a matroid analogue. We show that, as with cographs, both $2$-cographs and binary comatroids can be recursively defined. However, unlike cographs, $2$-cographs and binary comatroids are closed under induced minors. We consider the class of non-$2$-cographs for which every proper induced minor is a $2$-cograph and show that this class is infinite. Our main result for graphs finds the finitely many members of this class whose complements are also  induced-minor-minimal non-$2$-cographs. In the matroid case, our main result identifies all binary non-comatroids for which every proper flat is a binary comatroid. This is joint work with James Oxley.


Online Talk: Jim Geelen

Tuesday, Sept 28, 3pm ET (8pm BST, 8am Wed NZST)
Jim Geelen, University of Waterloo
Is this Ramsey’s Theorem for Matroids?

For a simple matroid $M$ with no lines of length $l$ or more, if the rank of $M$ is sufficiently large (as a function of $l$) and we $2$-colour the elements of $M$, is there necessarily a monochromatic line? We discuss this and a good many related problems.