This is a guest post by Mark Saaltink.

A $q$-analog is formed by replacing the notion of a set by the notion of a vector space, with a corresponding replacement of other concepts: cardinality becomes dimension, elements are replaced by 1-dimensional subspaces, the empty set is replaced by the 0-dimensional subspace, intersection remains the same, and union is replaced by sum. (It is not always clear how to replace set difference or symmetric difference.) The application of this idea to matroid theory gives the theory of q-matroids [Jur2018][Cer2022], which Relinde Jurrius has described in this forum, most recently with the analog of delta-matroids. In this post I’ll define a $q$-analog of a transversal [Mir1971], and show that there is still a connection with matroids, as well as analogs of many of the main theorems of transversal theory. A more complete account has been posted on arXiv.

$q$-matroids, briefly

A $q$-matroid can be characterized by its bases, independent sets, circuits, or spanning sets, but the simplest definition for our purposes is via the rank function.

Definition 0. Let $V$ be a vector space and ${\cal L}(V)$ be the lattice of subspaces of $V$. A $q$-matroid on $V$ is determined by a rank function $r: {\cal L}(V) \rightarrow \mathbb{Z}$, satisfying, for all $A, B \in {\cal L}(V)$,

1. $0 \leq r(A) \leq \dim A$ (rank is non-negative and bounded by dimension),
2. if $A \leq B$ then $r(A) \leq r(B)$ (rank is non-decreasing), and
3. $r(A \vee B) + r(A \wedge B) \leq r(A) + r(B)$ (rank is submodular).

The usual concepts of matroid theory apply equally well to $q$-matroids: a subspace $A$ is independent if $r(A) = \dim A$, and dependent otherwise; a subspace $A$ is a circuit if it is dependent but all its proper subspaces are independent; the closure of $A$ is the largest subspace $B$ with $A \leq B \leq V$ and $r(B) = r(A)$; and $A$ is spanning if its closure is $V$. Axiom systems for $q$-matroids in terms of independent sets, bases, or circuits can be found in [Cer2022].

The closure of the trivial subspace $\{ 0 \}$ gives the so-called loop space of the matroid; any subspace of rank 0 is contained in this loop space. A $q$-matroid of rank 1 is therefore completely characterized by its loop space $L$, with the rank of a subspace $X$ being 0 if it is a subspace of $L$ and 1 otherwise.

A large class of $q$-matroids can be defined algebraically; these are the representable $q$-matroids. Given some $n\times m$ matrix $G$ over a field $K$ extending $\mathbb{F}_q$, we can define the $q$-matroid represented by $G$ as follows: if a subspace of $\mathbb{F}_q^m$ is the row space of matrix $X$, then its rank in the $q$-matroid is the rank of $GX^T$. It can be seen that this does not depend on the matrix $X$ we use; if $X$ and $Y$ are full-rank matrices with equal row spans, then there is some invertible matrix $A$ so that $Y = AX$. Then $GY^T = GX^TA^T$, and as $A^T$ is invertible, the ranks are the same. Note that the entries of $G$ may lie in a larger field than the vector space is defined over. Usually $K$ is equal to $\mathbb{F}_{q^k}$ for some $k$.

Unlike a normal matroid that might be representable over fields of many different characteristics, a $q$-matroid representation has its characteristic fixed by the vector space the $q$-matroid is defined on. I suppose the interesting question about representations is then which extension fields are possible.

Normal transversals, abnormally

To have a clear connection to $q$-matroids, it seems to work best to analogize a cryptomorphic version of transversal theory. Where the usual definition has membership, this definition uses non-membership.

Definition Given an indexed family ${\cal X} = (X_1,X_2, \dotsc, X_n)$ of subsets of some given set $S$, an avoiding transversal of $\cal X$ is a set of elements $x_1, x_2, \dotsc, x_n$ of $S$, all distinct, with each $x_i \notin X_i$. A partial avoiding transversal of $\cal X$ is an avoiding transversal of some subfamily (that is, containing some subset of the $X_i$).

Clearly, when $A_i = S \setminus X_i$, an avoiding transversal of $\cal X$ is just a transversal of the $A_i$.

The main properties of transversals can be recast in this setting. We first define ${\cal X}(J) = \bigcap_{j\in J} X_j$ for any $J \subseteq \{1, 2, \dots,n\}$, with the convention ${\cal X}(\emptyset) = S$.

Theorem

1. (Hall) $\cal X$ has a transversal iff for all $J \subseteq \{1, 2, \dots,n\}$ we have $|{\cal X}(J)| + |J| \leq |S|$.
2. (Rado) Suppose $M$ is a matroid on $S$ with co-nullity function $\nu^*$. $\cal X$ has a transversal that is independent in $M$ iff for all $J \subseteq \{1, 2, \dots,n\}$ we have $\nu^*({\cal X}(J)) + |J| \leq \nu^*(S)$.
3. (Edmonds and Fulkerson) The set of partial transversals of $\cal X$ are the independent sets of a matroid.
4. (Piff and Welsh) Transversal matroids are representable over every sufficiently large field.
5. A matroid is transversal iff it is the union of a collection of rank-1 matroids.

When $M$ is the matroid whose independent sets are the partial avoiding transversals of $\cal X$ we say that $M$ is a transversal matroid and $\cal X$ is a co-presentation of $M$. Co-presentations have some nice properties:

1. If the rank of transversal matroid $M$ is $r$, then $M$ has a co-presentation with $r$ elements.
2. If $\cal X$ is a co-presentation of $M$ and the rank of $M$ is $r$, then $\cal X$ has a subfamily with $r$ elements that is also a co-presentation of $M$.
3. If $(X_1, \dots, X_r)$ is a co-presentation of $M$, then each $X_i$ is a flat.
4. If $M$ is a transversal matroid, then it has a unique minimal co-presentation, where a co-presentation is minimal if no members can be removed or replaced by strictly smaller sets while still co-representing $M$.

$q$-transversals, finally

In this section we will be talking about the vector space $V$ and its subspaces as well as $q$-matroids, so there is room for some confusion when we say “independent” or “basis”. Therefore we will qualify these terms and speak of a “vector basis” or “independent vectors” when referring to $V$ and its elements, or a “matroid basis” or “independent subspace” when referring to aspects of a $q$-matroid.

Definition Let a vector space $V$ be given, together with a family ${\cal X} = (X_1, \dotsc, X_n)$ of subspaces of $V$. A $q$-transversal is a dimension $n$ subspace $T$ of $V$ where every vector basis $B$ of $T$ has an ordering $B = \{b_1, \dots, b_n\}$ such that $b_i \notin X_i$ for $i \in\{1,2,\dotsc,n\}$. That is, every vector basis of $T$ is an avoiding transversal of $\cal X$. A partial $q$-transversal is a dimension $n$ subspace $T$ where every vector basis of $T$ is a partial avoiding transversal of $\cal X$.

The definition of partial $q$-transversal deserves some note. It would be more analogous to the conventional theory to declare a partial $q$-transversal to be a $q$-transversal of some subsystem of $\cal X$. This turns out to be equivalent, but is more difficult to work with. Analogs of the major properties of transversals are also enjoyed by $q$-transversals as defined this way:

Theorem

• Family $\cal X$ has a $q$-transversal iff for every nonempty $J \subseteq \{1, 2, \dots, n\}$ we have $\dim {\cal X}(J) + |J| \leq \dim V$.
• The set of partial $q$-transversals of a family form the independent subspaces of a $q$-matroid.
• A $q$-matroid is $q$-transversal iff it is the union of a collection of rank 1 $q$-matroids.

I conjecture that all $q$-transversal matroids are representable, but have only proven a special case where the spaces $X_i$ align is a particular way:

Theorem Suppose that $V$ has a vector basis $\{b_1, b_2, \dotsc, b_n\}$ so that each of the $X_i$ has the form $X_i = \left< b_i \,|\, i \in L_i \right>$ for some sets $L_i \subseteq \{1, 2, \dots, n \}$. Then the associated $q$-transversal matroid is representable.

I also conjecture that an analog of Rado’s theorem holds. Recall that if $\cal B$ is the set of bases of matroid $M$, then co-nullity satisfies $\nu^*(X) = \min_{B \in \cal B} | B \cap X |$, so we may plausibly define a $q$-analog $\bar n$ satisfying $\bar n(X) = \min_{B \in \cal B} \dim(B \wedge X)$ for a $q$-matroid $M$ with bases $\cal B$.

Conjecture Suppose $M$ is a $q$-matroid on vector space $V$, with rank function $r$, and $\cal X$ is a system of subspaces of $V$. Then $\cal X$ has a $q$-transversal that is independent in $M$ iff for all $J \subseteq I$ we have $\bar n ({\cal X}(J)) + |J| \leq \bar n (V)$.

When $M$ is the $q$-matroid whose independent spaces are the set partial $q$-transversals of a family $\cal X$ we say that $M$ is $q$-transversal and that $\cal X$ is a presentation of $M$.

1. If the rank of $q$-transversal matroid $M$ is $r$, then $M$ has a presentation with $r$ elements.
2. If $\cal X$ is a presentation of $q$-matroid $M$ and the rank of $M$ is $r$, then $\cal X$ has a subfamily with $r$ elements that is also a presentation of $M$.
3. If $(X_1, \dots, X_r)$ is a presentation of $M$, then each $X_i$ is a flat.

I conjecture that any $q$-transversal matroid has a unique minimal presentation.

As can be seen, while there are still some interesting questions to be settled, the analogy with normal transversal theory looks promising. Details and proofs are in the paper on arXiv [Saa2025].

References

[Cer2002] Michela Ceria and Relinde Jurrius. Alternatives for the $q$-matroid axioms of independent spaces, bases, and spanning spaces. arXiv.org/abs/2207.07324v3, December 2022.

[Jur2018] Relinde Jurrius and Ruud Pellikaan. Defining the $q$-analog of a matroid. Article #P3.2, The Electronic Journal of Combinatorics 25(3), 2018.

[Mir1971] Leon Mirsky. Transversal Theory: an account of some aspects of combinatorial mathematics. Academic Press, 1971.

[Saa2025] Mark Saaltink. A theory of $q$-transversals arXiv.org/abs/2503.12201, March 2025.

Guest post by James Oxley.

1. Introduction

It is well known that a graph is bipartite if and only if every cycle has an even number of edges and that a connected graph is Eulerian if and only if every vertex has even degree. While we cannot characterize arbitrary matroids in which every circuit has even cardinality, we can characterize binary matroids with this property. For reasons that will be clarified later, such a binary matroid is called affine.  The goal of this note is to prove the following two theorems. The first is due to Jim Geelen and Peter Nelson, the second to Nathan Bowler. A circuit $C$ in a matroid is odd if $|C|$ is odd; otherwise $C$ is even.

Theorem 1.1 (Geelen and Nelson).  Let $M$ be a loopless, connected, non-affine, binary matroid. If a largest odd circuit of $M$ has $k$ elements, then $M$ has no circuit of size exceeding $2k-2$.

Theorem 1.2 (Bowler). Let $n$ and $k$ be integers exceeding two where $k$ is odd. Then there is an integer $N(k,n)$ such that every $3$-connected, non-affine, binary matroid whose largest odd circuit has $k$ elements either has at most $N(k,n)$ elements or has a minor isomorphic to $M(K_{3,n})$. 

Both of these theorems emerged two years ago from discussions following the author’s online seminar talk [7] based on the paper by Chun, Oxley, and Wetzler [2]. The proofs of these theorems were emailed to the author by Jim Geelen and Nathan Bowler.  The matroid terminology used here will follow [6].

2. Background

Recall that the rank-$r$ binary projective geometry $PG(r-1,2)$ is the matroid whose elements are the non-zero vectors of $V(r,2)$, the $r$-dimensional vector space over the two-element field, and whose independent sets are the linearly independent subsets of $V(r,2)$. For example, the matroids $PG(0,2)$, $PG(1,2)$, and $PG(2,2)$ are $U_{1,1}$, $U_{2,3}$, and the Fano matroid. Of course, every simple binary matroid of rank $r$ is isomorphic to a restriction of $PG(r-1,2)$.  The rank-$r$ binary affine geometry $AG(r-1,2)$ is the matroid that is obtained from $PG(r-1,2)$ by deleting one of its hyperplanes. Thus $AG(0,2)$, $AG(1,2)$, and $AG(2,2)$ are $U_{1,1}$, $U_{2,2}$, and $U_{3,4}$. Clearly, $AG(r-1,2)$ is the matroid that is obtained from $V(r,2)$ by deleting a $V(r-1,2)$. The symmetry of $V(r,2)$ means that it does not matter which hyperplane we choose to delete. If we delete the hyperplane consisting of the vectors whose first coordinate is zero, then we see that the elements of $AG(r-1,2)$ are the vectors of $V(r,2)$ whose first coordinate is one. It follows that every circuit of $AG(r-1,2)$ is even. To see that a simple binary matroid $M$ having no odd circuits is a restriction of a binary affine geometry, we proceed as follows. Let $A$ be a binary matrix representing $M$. Adjoin a new row to $A$ consisting entirely of ones to get the matrix $A^+$. Then one easily checks that $M[A] = M[A^+]$. Clearly $M[A^+]$ is a restriction of a binary affine geometry.

Adding elements in parallel to existing elements of a simple binary affine matroid yields another binary matroid in which every circuit is even. We deduce that a binary matroid is affine if and only if it has no loops and its simplification is isomorphic to a restriction of a binary affine geometry. The next theorem, which incorporates this observation, is obtained by combining results of Brylawski [1], Heron [4], and Welsh [8]. A proof of the equivalence of i and ii was outlined above. A proof of the equivalence of i and iii may be found in [6, Proposition 9.4.1]. This equivalence, originally shown by Welsh, generalizes to binary matroids the dual relationship between bipartite and Eulerian graphs.

Theorem 2.1.  The following are equivalent for a non-empty binary matroid $M$.

1. Every circuit of $M$ is even.
2. $M$ is loopless and its simplification is isomorphic to a restriction of a binary affine geometry. 
3. $E(M)$ can be partitioned into cocircuits.

3. Proofs and Consequences

This section presents the proofs of the two main theorems. The proof of Theorem 1.1 will use the next two lemmas. A theta-graph is a graph $G$ consisting of two vertices, $u$ and $v$, and three internally disjoint paths joining them. These three $uv$-paths in $G$ are the series classes of the theta-graph.

Lemma 3.1. In a connected binary matroid $M$ with an element $e$ and an odd circuit $C$, either $E(M) = C$, or $M$ has as a restriction the cycle matroid of a theta-graph that contains the element $e$ and has $C$ as the union of two of its series classes. In particular, $M$ has an odd circuit containing $e$.

Proof. We may assume that $E(M) \neq C$. Let $d$ be an element of $E(M) – C$, and let $D$ be a circuit that contains $d$ and meets $C$ such that $D – C$ is minimal. As $M$ is binary, $C \bigtriangleup D$ is a disjoint union of circuits. The minimality of $D- C$ implies that $C \bigtriangleup D$ is a circuit, so $M|(C \cup D)$ is the cycle matroid of a theta-graph in which $C$ is the union of two of the series classes. To ensure that $e \in C \cup D$, we take $e = d$ when $e \notin C$. Because the series classes in $M|(C \cup D)$ do not all have even cardinality, it follows that $e$ is in an odd circuit of $M$.

Lemma 3.2. Let $M$ be a connected, non-affine binary matroid. If $M|X$ is connected and affine having at least two elements, then $M$ has an odd circuit $D$ that meets both $X$ and $E(M) – X$ for which $D-X$ is a circuit of $M/X$. Moreover, if $X$ is a circuit, then $M|(X\cup D)$ is the cycle matroid of a theta-graph in which exactly two of the series classes have the same parity.

Proof. As $M$ is not affine, it has an odd circuit $C$. Thus, by Lemma 3.1, $M$ has an odd circuit containing $e$. Hence we can take an odd circuit $D$ that meets $X$ for which $D – X$ is minimal. Suppose that $D -X$ is not a circuit of $M/X$. Then $M/X$ has a circuit $D_1$ that is properly contained in $D -X$. Thus $M$ has a circuit $D_2$ that meets $D-X$ in $D_1$ and is contained in $D_1 \cup X$. The choice of $D$ implies that $D_2$ is even. Now $D \bigtriangleup D_2$ is a disjoint union of circuits of $M$. As $|D \bigtriangleup D_2|$ is odd, $D \bigtriangleup D_2$ contains an odd circuit. This odd circuit cannot be contained in $X$, nor does it contain $D-X$. Hence it contradicts the choice of $D$. Thus $D -X$ is a circuit of $M/X$.  It follows immediately that if $X$ is a circuit, then $M|(X\cup D)$ is the cycle matroid of a theta-graph. As each of $D$ and $X$ is the union of exactly two of the series classes in this theta-graph, and $|D|$ and $|X|$ have different parities, it follows that exactly two of the series classes in $M|(X\cup D)$ have the same parity.

Proof of Theorem 1.1.  Let $C$ be a largest circuit of $M$. We may assume that $C$ is even. By Lemma 3.2, $M$ has an odd circuit $D$ that meets $C$ such that $M|(C\cup D)$ is the cycle matroid of a theta-graph. Let the series classes of the theta-graph be $S_1$, $S_2$, and $S_3$ where the first two have the same parity. Then $C = S_1 \cup S_2$.
Suppose that each of $|S_1 \cup S_3|$ and $|S_2 \cup S_3|$ is at most $\tfrac{1}{2}|C|$. Then $|S_1| + |S_2| + 2|S_3| \le |S_1| + |S_2|$. Thus $S_3$ is empty, a contradiction. Hence $|S_1 \cup S_3|$ or $|S_2 \cup S_3|$ exceeds $\tfrac{1}{2}|C|$, and the theorem follows.

A theta-graph with two series classes each having $k – 1$ elements and one having exactly one element shows that the bound in Theorem 1.1 is sharp.  Another immediate consequence of Lemma 3.2 is the following.

Corollary 3.3. Every even circuit in a connected, non-affine, binary matroid is the symmetric difference of two odd circuits.

In a connected matroid $M$ with at least two elements, the sizes of a largest circuit and a largest cocircuit are the circumference $c(M)$ and the cocircumference $c^*(M)$, respectively. When $M$ has an odd circuit, we denote the size of a largest odd circuit by $c_o(M)$; when $M^*$ has an odd circuit, we write $c^*_o(M)$ for $c_o(M^*)$.

Corollary 3.4. Let $M$ be a connected binary matroid having an odd circuit and an odd cocircuit. Then
$$|E(M)| \le 2(c_o(M) – 1)(c^*_o(M) – 1).$$

Proof. By a result of Lemos and Oxley [5], $|E(K)| \le \tfrac{1}{2}c(K)c^*(K)$ for all connected matroids $K$. Combining this with Theorem 1.1 gives the result.

In the next proof, $M({\mathcal W}_m)$ denotes the cycle matroid of a rank-$m$ wheel, while a tipless binary spike of rank $m$ is the vector matroid of the binary matrix $[I_m|I_m^c]$ where $I_m^c$ is the $m \times m$ matrix that is obtained from $I_m$ by replacing each entry by the other element in the two-element field.

Proof of Theorem 1.2. Let $m = \max\{n, 2k -1\}$. By a theorem of Ding, Oporowski, Oxley, and Vertigan [3], there is a number $N(m)$ such that every $3$-connected binary matroid having more than $N(m)$ elements has as a minor one of $M({\mathcal W}_m)$, $M(K_{3,m})$, $M^*(K_{3,m})$, or a tipless binary spike of rank $m$. If $M$ is a non-affine such matroid and its largest odd circuit has $k$ elements, then, by Theorem 1.1, its largest circuit has at most $2k-2$ elements. Each of $M({\mathcal W}_m)$, $M^*(K_{3,m})$, and the tipless binary spike of rank $m$ has an $m$-element circuit, so none of these matroids occurs as a minor of $M$. Hence $M$ has a minor isomorphic to $M(K_{3,m})$. Taking $N(k,n)$ to be $N(m)$, we get the theorem.

Corollary 3.5. For every odd integer $k$ exceeding two, there is an integer $N'(k)$ such that every $3$-connected, non-Eulerian, simple graph whose largest odd bond has $k$ edges has at most $N'(k)$ edges.

Bibliography

[1] T.H. Brylawski, A decomposition of combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235-282.

[2] C. Chun, J. Oxley, K. Wetzler, The binary matroids with no odd circuits of size exceeding five, J. Combin. Theory Ser. B 152 (2022), 80-120.

[3] G. Ding, B. Oporowski, J. Oxley, and D. Vertigan, Unavoidable minors of large $3$-connected binary matroids, J. Combin. Theory Ser. B 66 (1996), 334-360.

[4] A.P. Heron, Some topics in matroid theory, D.Phil. thesis, University of Oxford, 1972.

[5] M. Lemos and J. Oxley, A sharp bound on the size of a connected matroid, Trans. Amer. Math. Soc. 353 (2001), 4039-4056.

[6] J. Oxley, Matroid Theory, Second edition, Oxford University Press, New York, 2011.

[7] J. Oxley, The binary matroids with no odd circuits of size exceeding five, Graphs and Matroids Online Seminar, University of Waterloo, April 17, 2020.

[8] D.J.A. Welsh, Euler and bipartite matroids, J. Combin.Theory 6 (1969), 313-316.

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.