Matroid union theorem
From Egres Open
Theorem (Edmonds [1], Nash-Williams [2]). Let [math]M_1=(S_1,r_1),M_2=(S_2,r_2),\dots,M_k=(S_k,r_k)[/math] be matroids, where [math]S_1,\dots, S_k[/math] are not necessarily disjoint, and let [math]S=S_1\cup\dots\cup S_k[/math]. The collection of subsets of [math]S[/math] that are of the form [math]X_1 \cup\dots \cup X_k[/math], where [math]X_i[/math] is independent in [math]M_i[/math], form a matroid. The rank function of this matroid is [math]r(X)=\min_{Y \subseteq X}(|X \setminus Y|+r_1(S_1 \cap Y)+\dots+r_k(S_k \cap Y)).[/math]
The matroid union theorem can be derived from Edmonds' matroid intersection theorem, and vice versa.
References
- ↑ J. Edmonds, Matroid Partition, Math. of the Decision Sciences, Amer. Math Soc. Lectures in Appl. Math. 11 (1968), 335–345, DOI link, author link
- ↑ C.St.J.A. Nash-Williams, An application of matroids to graph theory, in: Theory of Graphs - International Symposium (Rome, 1966; P. Rosenstiehl, ed.), Gordon and Breach, New York, and Dunod, Paris, 1967, pp. 263-265.
