Matroid union theorem

From Egres Open
Jump to: navigation, search

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.


  1. J. Edmonds, Matroid Partition, Math. of the Decision Sciences, Amer. Math Soc. Lectures in Appl. Math. 11 (1968), 335–345, DOI link, author link
  2. 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.