OctoInformBeta

Counterexamples to infinite matroid intersection and packing/covering

The matroids here are infinite matroids in the sense of Bruhn, Diestel, Kriesell, Pendavingh and Wollan, whose axioms provide restriction, contraction and duality. For a matroid MM on EE and X⊆EX\subseteq E, the contraction of MM onto XX is M.X=M/(E\X)M.X=M/(E\setminus X). A packing/covering partition of a family (Mi:i∈Θ)(M_i:i\in\Theta) of matroids on EE is a partition E=P∪̇CE=P\mathbin{\dot\cup}C together with pairwise disjoint sets Si⊆PS_i\subseteq P, each spanning the restriction Mi↾PM_i\upharpoonright P, and sets Ii⊆CI_i\subseteq C, each independent in Mi.CM_i.C, whose union is CC. The infinite matroid packing/covering conjecture asserts that every family of matroids on a common ground set, indexed by a set, has a packing/covering partition. A pair (M,N)(M,N) of matroids on EE satisfies intersection if some set JJ independent in both has a partition J=JM∪̇JNJ=J_M\mathbin{\dot\cup}J_N with cl⁡M(JM)∪cl⁡N(JN)=E\operatorname{cl}_M(J_M)\cup\operatorname{cl}_N(J_N)=E. The unrestricted infinite Matroid Intersection Conjecture asserts that every pair of matroids on a common ground set satisfies intersection. A matroid MM is self-dual if M*=MM^*=M on the same labelled ground set. Uniform matroids are those in which every subset of the ground set is independent or spanning. A matroid is partitional if, up to relabelling, it is a direct sum of uniform matroids. A matroid is finitary if a set is independent whenever all its finite subsets are independent. A matroid is cofinitary if its dual is finitary.

Bowler and Carmesin formulated the packing/covering conjecture. They proved that a pair (M,N)(M,N) of matroids on one ground set satisfies intersection if and only if (M,N*)(M,N^*) has a packing/covering partition. Nash-Williams’ original intersection conjecture, in an early published formulation by Aharoni and Ziv, concerned finitary matroids. Joó proved intersection for two finitary matroids on a countable ground set. Joó later proved that every family of matroids on a countable ground set, indexed by a set, whose members are direct sums of finitary and cofinitary matroids has a packing/covering partition. Intersection for an arbitrary matroid paired with a direct sum of finitely many uniform matroids was also proved by Joó. He asked there whether intersection holds for two partitional matroids on a common countable ground set. Bowler and Geschke constructed self-dual uniform matroids on a countably infinite set under Martin’s axiom for countable partially ordered sets, and hence under the continuum hypothesis. They left open whether an infinite self-dual uniform matroid can be constructed in ZFC.

The preprint proves in ZFC that there are a countably infinite set EE and two self-dual matroids M0,M1M_0,M_1 on EE such that I0∪I1≠EI_0\cup I_1\neq E for every independent set I0I_0 of M0M_0 and every independent set I1I_1 of M1M_1. The pair (M0,M1)(M_0,M_1) has no packing/covering partition. It also does not satisfy intersection. Both M0M_0 and M1M_1 are partitional. The preprint also constructs in ZFC a self-dual uniform matroid QQ on a countably infinite set. It further shows that neither M0M_0 nor M1M_1 has a nonempty finitary or cofinitary direct summand, which the Lean library does not contain.

The results on these pages are those of the Lean library InfiniteMatroid, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library, so the Lean library is the reference. Where the preprint states a result differently, the statement on its page is the Lean library’s, with the preprint’s beside it. The preprint is a guide only: it gives the results their order and their names.

The Lean library: InfiniteMatroid

InfiniteMatroid is a Lean library: 31 items, in seven groups. Each has a page written by OctoInform, listed below.

§1. Introduction 4 items
  1. Packing/covering partitions and contraction onto a set The ground sets and the packing/covering partition of two matroids. §1
  2. Intersection, uniform and partitional matroids Matroid intersection and partitional matroids as sums of uniform ones. §1
  3. Theorem 1.1 A counterexample to the infinite matroid packing/covering conjecture.
  4. Corollary 1.2 Intersection fails for two partitional matroids on a countable set.
§2. Matroids and the self-dual reduction 1 item
  1. Lemma 2.2 For self-dual matroids, packing/covering partitions give covers by independent sets.
§3. An ultrafilter rank and simultaneous reservations 7 of 8 written
  1. Blocks and the density-zero ideals 𝒥 and 𝒥_0 Doubly exponential blocks and the ideals of density zero. §3
  2. Ideals, ⊆_𝒦, and the larger ideals 𝒦 and 𝒦_0 A proper ideal containing the complement of every AA-column. §3
  3. Lemma 3.1 not yet written
  4. Lemma 3.2 Positive signed patterns yield an ultrafilter avoiding the ideal.
  5. The ordinal rank ρ (3.4) Large sets ranked by ordinals below the continuum. §3
  6. Lemma 3.3 Small changes preserve largeness and rank.
  7. Lemma 3.4 Large sets have large subsets of arbitrarily high ordinal rank.
  8. Lemma 3.5 Simultaneous reservations for fewer than 𝔠\mathfrak c positive sets.
§4. Bases within a density-zero class 7 items
  1. The class 𝒞(T), the probes and the rules ℬ^- and ℬ^+ (4.1), (4.2) Probes and two rules within a density-zero class. §4
  2. Lemma 4.1 Normalized probes vanish in a density-zero class, and the probes are monotone.
  3. Lemma 4.2 Probes are continuous on intervals of a density-zero class.
  4. Lemma 4.3 Both local rules at TT contain TT and are antichains.
  5. Lemma 4.4 Density-zero changes can send the probes to ±∞\pm\infty.
  6. Lemma 4.5 Interpolation inside a density-zero class by lower limits of probes.
  7. Proposition 4.6 When a local rule meets an interval of sets.
§5. Assembling a self-dual matroid 7 items
  1. Admissible sets and the two zones (5.1) Admissible sets and the upper and lower zones. §5
  2. Lemma 5.1 Upper, Lower and admissible zones partition the subsets of E0E_0.
  3. Lemma 5.2 An admissible set lies between nested lower and upper sets.
  4. Lemma 5.3 Inserting an admissible set separated from fewer than 𝔠\mathfrak c sets.
  5. Proposition 5.4 A basis system whose members are all admissible.
  6. Theorem 5.5 Basis systems are base families of self-dual matroids.
  7. Remark 5.6 The matroid of a basis system is uniform.
§6. Two matroids on a double ray (proof of Theorem 1.1) 2 items
  1. The double ray, the copies Q_n and the sums M_0, M_1 Summing copies of a matroid along a double ray. §6
  2. The descending ranks (6.2) The ray matroids of QQ admit no independent cover. §6
§7. The separate Covering and Packing conjectures 2 items
  1. The Covering (7.1) and Packing (7.2) conjectures The Covering and Packing Conjectures for a family of matroids. §7
  2. Corollary 7.1 Counterexamples to the separate Covering and Packing Conjectures.

No item matches.