A Cantor-Bernstein Result for Trees

The following is a summary of A Cantor-Bernstein-type theorem for spanning trees in infinite graphs [EGJKP2021a] and Base Partition for Mixed Families of Finitary and Cofinitary Matroids [EGJKP2021b] which are joint work with Joshua Erde, J. Pascal Gollin, Attila Joó and Max Pitz. In 2021 the former is published in Journal of Combinatorial Theory, Series B, and the latter in Combinatorica. You can find their preprints on arXiv.

Main results

1.) The edge set set of a graph G admits a partition into λ spanning trees if and only if it contains λ edge-disjoint spanning trees and is also covered by λ spanning trees [EGJKP2021a, Theorem 1.1] [EGJKP2021b, Corollary 1.3].

2.) Let 𝒨 be a family of matroids on a common ground set E each of which is either finitary or cofinitary. Then 𝒨 admits a base partitioning if and only if it admits both a base covering and a base packing [EGJKP2021b, Theorem 1.2].

Summary

If the edge set of a finite graph G is covered by λ spanning trees, then G has so few edges that any λ edge-disjoint spanning tress must already partition E(G). However, this argument fails when the edge set of G is infinite, even if λ is finite. Our 1st main result extends this to infinite graphs and arbitrary cardinals λ. It follows directly from our 2nd main result which is its generalisation to families of (co-)finitary matroids. Later Joó [Joó23] found a much shorter and elegant proof.

References

[Joó23] A. Joó, A Cantor–Bernstein theorem for infinite matroids, Journal of Combinatorics 14.2 (2023): 257-270. Available at arXiv:2009.08439.