Base Partition for Mixed Families of Finitary and Cofinitary Matroids
- PDF / 466,417 Bytes
- 22 Pages / 442.205 x 665.008 pts Page_size
- 45 Downloads / 187 Views
Bolyai Society – Springer-Verlag
Combinatorica 22pp. DOI: 10.1007/s00493-020-4422-4
BASE PARTITION FOR MIXED FAMILIES OF FINITARY AND COFINITARY MATROIDS ´ † , PAUL JOSHUA ERDE, J. PASCAL GOLLIN∗ , ATTILA JOO KNAPPE, MAX PITZ Received January 17, 2020 Revised June 5, 2020 Let M = (Mi : i ∈ K) be a finite or infinite family consisting of matroids on a common ground set E each of which may be finitary or cofinitary. We prove the following CantorBernstein-type result: If there is a collection of bases, one for each Mi , which covers the set E, and also a collection of bases which are pairwise disjoint, then there is a collection of bases which partition E. We also show that the failure of this Cantor-Bernstein-type statement for arbitrary matroid families is consistent relative to the axioms of set theory ZFC.
1. Introduction 1.1. The main result Our starting point and main motivation was the following problem in infinite graph theory: Let G = (V, E) be a connected graph. Given a cardinal λ, a family (Ti : i < λ) of spanning trees of G is called • a λ-covering of G if the union of the E(Ti ) is E, • a λ-packing of G if the Ti are pairwise edge-disjoint, and • a λ-partitioning of G if (E(Ti ) : i < λ) is a partition of E. Does the existence of a λ-covering and a λ-packing imply the existence of a λpartitioning? Recently, we have proved that this holds when λ is infinite [11]: Mathematics Subject Classification (2010): 05B35, 05B40, 05C63; 03E35 The second author was supported by the Institute for Basic Science (IBS-R029-C1). † The third author would like to thank the generous support of the Alexander von Humboldt Foundation and NKFIH OTKA-129211. ∗
2
´ P. KNAPPE, M. PITZ J. ERDE, J. P. GOLLIN, A. JOO,
Theorem 1.1. Let λ be an infinite cardinal. Then a graph admits a λpartitioning if and only if it admits both a λ-packing and a λ-covering. The point of departure for this paper is the natural question of whether the corresponding result also holds for finite λ. Note that, when G is finite the result is clearly true, since the existence of a λ-covering implies that G has so few edges that any λ-packing must be a λ-partitioning. However, this argument fails when the edge set of G is infinite, even if λ is finite. As is often the case when considering spanning trees in graphs, there is a natural generalisation of the problem to a question about bases in matroids, and indeed our proof was influenced by this change in view. Recall that for every connected graph G = (V, E), finite or infinite, there is a matroid M (G) with ground set E whose circuits are the subsets of E given by the cycles of G, and whose bases are precisely the subsets of E given by spanning trees of G. Every matroid of the form M (G) is finitary: it has the property that all of its circuits are finite. Recently, there has been a renewed interest in the theory of infinite matroids, after Bruhn, Diestel, Kriesell, Pendavingh and Wollan [8] gave a set of cryptomorphic axioms for infinite matroids which encompasses duality, generalising the usual indepen
Data Loading...
