Talk:Matroid partitioning
Add topic | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Matroid partitioning algorithm implies matroid sum is a matroid
[edit]The article currently writes:
[The matroid partitioning algorithm's] correctness can be used to prove that a matroid sum is necessarily a matroid.[1][2]
However, I cannot find justification for this sentence in the sources cited. As far as I can tell, neither of the sources explicitly proves that the matroid sum is a matroid, and it is not obvious to me how it follows. Oxley's textbook[3] shows that the matroid sum is a matroid (Theorem 11.3.1) by proving it is induced across a bipartite graph by the direct sum matroid; in turn, the "matroid induced across a bipartite graph by another matroid" is shown to be a matroid using submodular functions (Theorem 11.2.12). Generally the proofs I've found of this fact all use submodular functions rather than the matroid partitioning algorithm.
So, can anyone find a citation proving that the matroid sum is a matroid using the matroid partitioning algorithm, or explain why this is present in the existing sources?
Elestrophe (talk) 19:59, 12 March 2026 (UTC)
- ↑ Edmonds, Jack (1965), "Minimum partition of a matroid into independent subsets" (PDF), Journal of Research of the National Bureau of Standards, 69B: 67–72, doi:10.6028/jres.069b.004, MR 0190025
- ↑ Gabow, Harold N.; Westermann, Herbert H. (1992), "Forests, frames, and games: algorithms for matroid sums and applications", Algorithmica, 7 (5–6): 465–497, doi:10.1007/BF01758774, MR 1154585
- ↑ Oxley, James (1992). Matroid Theory. Oxford, UK: Oxford University Press. ISBN 978-0-19-853563-8. MR 1207587. Zbl 0784.05002.