On generalisations of the Aharoni–Pouzet base exchange theorem

DOI10.1112/BLMS.12808MaRDI QIDQ6096802zbMATH OpenOpenAlexWikidataFDO

Authors Zsuzsanna Jankó, Attila Joó

Publication date 15 September 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2204.09326

zbMATH Keywords

Greene-Magnanti theorem

Mathematics Subject Classification ID

Other combinatorial set theory (03E05) Partitions of sets (05A18) Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial aspects of packing and covering (05B40) Trees (05C05) Vector spaces, linear dependence, rank, lineability (15A03)

Abstract: The Greene-Magnanti theorem states that if $M$ is a finite matroid, $B_0$ and $B_1$ are bases and $$ is a partition, then there is a partition $$ such that $(B_{0}setminus{X}_i)cup{Y}_i$ is a base for every $i$. The special case where each $X_i$ is a singleton can be rephrased as the existence of a perfect matching in the base transition graph. Pouzet conjectured that this remains true in infinite dimensional vector spaces. Later he and Aharoni answered this conjecture affirmatively not just for vector spaces but for infinite matroids. We prove two generalisations of their result. On the one hand, we show that `being a singleton' can be relaxed to `being finite' and this is sharp in the sense the exclusion of infinite sets is really necessary. On the other hand, we prove that if $B_0$ and $B_1$ are bases, then there is a bijection $F$ between their finite subsets such that $(B_{0}setminusI)cupF(I)$ is a base for every $I$. In contrast to the approach of Aharoni and Pouzet, our proofs are completely elementary, they do not rely on infinite matching theory.

Recommendations

• Bases in Infinite Matroids
• A matroid generalization of theorems of Lewin and Gallai
• A generalised exchange theorem for matroid bases
• On sequential basis exchange in matroids
• INFINITE MATROIDAL VERSION OF HALL'S MATCHING THEOREM

Cites work

• A compactness result for perfect matchings
• A compactness theorem for perfect matchings in matroids
• A generalised exchange theorem for matroid bases
• A Multiple Exchange Property for Bases
• Abstract linear dependence
• An Exchange Theorem for Independence Structures
• Axioms for infinite matroids
• Base partition for mixed families of finitary and cofinitary matroids
• Bases in Infinite Matroids
• Equicardinality of Bases in B-Matroids
• scientific article; zbMATH DE number 49099 (Why is no real title available?)
• INFINITE MATROIDAL VERSION OF HALL'S MATCHING THEOREM
• Matroids and duality
• On sequential basis exchange in matroids
• Self-dual uniform matroids on infinite sets
• Some Abstract Pivot Algorithms
• The Intersection of Two Infinite Matroids
• Transversals and matroid partition

Cited in

(5)

• On Pimsner-Popa bases
• The base change in the Atiyah and the Lück approximation conjectures
• A generalised exchange theorem for matroid bases
• Bases in Infinite Matroids
• A note on matching variables to equations

This page was built for publication: On generalisations of the Aharoni–Pouzet base exchange theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6096802)