Talk:Matroid partitioning

Matroid partitioning algorithm implies matroid sum is a matroid

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)[reply]

  1. ^ 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
  2. ^ 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
  3. ^ Oxley, James (1992). Matroid Theory. Oxford, UK: Oxford University Press. ISBN 978-0-19-853563-8. MR 1207587. Zbl 0784.05002.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.