Tuesday, Nov 2, 3pm EDT (7pm GMT, 8am Wed NZDT)
Relinde Jurrius, Netherlands Defence Academy
The direct sum of q-matroids
Monthly Archives: October 2021
For classical matroids, the direct sum is one of the most straightforward methods to make a new matroid out of existing ones. This talk focusses on the direct sum of q-matroids, the q-analogues of matroids. This is a lot less straightforward than in the classical case, as I will try to convince the audience. We will see a definition of the direct sum for q-matroids, using q-polymatroids and matroid union. As a motivation for this definition, I will list several desirable properties of this construction.
Online Talk: Natalie Behague
Tuesday, Oct 26, 3pm ET (8pm BST, 8am Wed NZST)
Natalie Behague, Ryerson University
Subgraph Games in the Semi-random Graph Process
Abstract:
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