15 Matroid union and Edmonds’ partition theorem
This chapter defines the union of finitely many matroids on a common finite set, describes its independent sets, and computes its rank. The rank formula is the matroid-union theorem of Nash-Williams [ NW67 ] and Edmonds. For \(k\) copies of one matroid \(M\), its independence criterion is Edmonds’ matroid-partition theorem [ Edm65 , Theorem 1 ] (theorem 15.11): a set can be partitioned into \(k\) independent sets of \(M\) if and only if every subset \(Y\) of it has at most \(k\, r_M(Y)\) elements. We follow Oxley’s presentation [ Oxl11 , § § 11.1–11.3 ] .
In section 15.1 we show that a non-decreasing integer-valued submodular function \(f\) on the subsets of a finite set \(E\) induces a matroid \(M_f\) on \(E\), and we compute the rank function of \(M_f\) when \(f(\emptyset ) = 0\). In section 15.2 we define the union \(\bigcup _j M_j\) of matroids \(M_1, \dots , M_k\) on \(E\) as the matroid induced from their direct sum by a bipartite graph. Its independent sets are the sets \(I_1 \cup \dots \cup I_k\) with each \(I_j\) independent in \(M_j\). By Rado’s theorem on independent transversals, the union is the matroid \(M_f\) of the function \(f(Y) = \sum _j r_{M_j}(Y)\), and the rank formula for \(M_f\) gives its rank.
In section 16 we apply these results to \(k\) copies of the cycle matroid of a multigraph. There the independence criterion becomes \((k, k)\)-sparsity, and it gives the tree-packing theorem of Tutte and Nash-Williams [ Tut61 , NW61 ] .
The formal proofs of this chapter come from Peter Nelson’s matroid package for Lean, apnelson1/Matroid, which, like this project, is licensed under Apache-2.0. In the package they rest on a matroid constructor that it has since replaced. We port them onto its current constructor, keeping his authorship, and add the forms of the rank formula proved for theorem 15.10. The header of each ported file lists the changes.
15.1 Matroids from submodular functions
Let \(E\) be a finite set. The rank function \(r\) of a matroid on \(E\) is non-decreasing and submodular, and the circuits of the matroid are the minimal non-empty sets \(C\) with \(r(C) {\lt} |C|\). By a result of Edmonds and Rota, every non-decreasing integer-valued submodular function \(f\) defines a matroid \(M_f\) in the same way, and when \(f(\emptyset ) = 0\) the rank function of \(M_f\) is given by a minimization formula [ Oxl11 , § 11.1 ] . We follow Oxley’s proofs. For \(M_f\), the circuit elimination axiom follows from the submodularity of \(f\) [ Oxl11 , Proposition 11.1.1 ] . Edmonds [ Edm70 ] studies these functions and the polyhedra they define.
Let \(E\) be a finite set. A function \(f\) from the subsets of \(E\) to the integers is submodular if \(f(X \cap Y) + f(X \cup Y) \le f(X) + f(Y)\) for all \(X, Y \subseteq E\).
A polymatroid rank function on a finite set \(E\) is a non-decreasing submodular function \(f\) on the subsets of \(E\) with \(f(\emptyset ) = 0\).
Let \(f\) be a non-decreasing submodular function on the subsets of a finite set \(E\). The matroid induced by \(f\) is the matroid \(M_f\) on \(E\) whose circuits are the minimal non-empty sets \(C \subseteq E\) with \(f(C) {\lt} |C|\). Equivalently, a set \(I \subseteq E\) is independent in \(M_f\) if and only if \(|I'| \le f(I')\) for every non-empty \(I' \subseteq I\).
Let \(f\) be a polymatroid rank function on a finite set \(E\). The matroid \(M_f\) is the matroid on \(E\) induced by \(f\) (definition 15.3). Its independent sets are the sets \(I \subseteq E\) with \(|I'| \le f(I')\) for every non-empty \(I' \subseteq I\).
Let \(f\) be a polymatroid rank function on a finite set \(E\), and let \(X \subseteq E\). Then the rank of \(X\) in \(M_f\) is
Let \(B\) be a basis of \(X\) in \(M_f\), so that \(r_{M_f}(X) = |B|\). Let \(Y \subseteq X\). The set \(B \cap Y\) is independent, so \(|B \cap Y| \le f(B \cap Y)\) (definition 15.3; if \(B \cap Y\) is empty, because \(f(\emptyset ) = 0\)). As \(f\) is non-decreasing, \(f(B \cap Y) \le f(Y)\). Also \(|B \setminus Y| \le |X \setminus Y|\). Hence \(|B| \le f(Y) + |X \setminus Y|\).
For the reverse inequality we follow Oxley’s proof [ Oxl11 , Proposition 11.1.7 ] . If \(X\) is independent, then \(Y = \emptyset \) attains \(|B|\). Otherwise, for each \(e \in X \setminus B\) the set \(B \cup \{ e\} \) is dependent, so it contains a circuit \(C_e\) of \(M_f\), and \(e \in C_e\). The set \(I_e = C_e \setminus \{ e\} \) is an independent subset of \(B\), and \(f(C_e) \le |C_e| - 1 = |I_e|\) (definition 15.3). Let \(Y\) be the union of the sets \(C_e\).
We show that \(f(Y) \le |Y \cap B|\), adding the sets \(C_e\) one at a time. A single \(C_e\) satisfies it, as \(C_e \cap B = I_e\). Let \(A\) be a union of some of them with \(f(A) \le |A \cap B|\), and let \(C_a\) be another. Each \(C_e\) lies in \(B \cup \{ e\} \), so \(a \notin A\). Hence \(A \cap C_a\) lies in the independent set \(I_a\), and \(f(A \cap C_a) \ge |A \cap I_a|\). By submodularity,
Finally, \(Y\) contains \(X \setminus B\), so \(X \setminus Y = B \setminus Y\), and \(f(Y) + |X \setminus Y| \le |Y \cap B| + |B \setminus Y| = |B|\).
15.2 Matroid union
Let \(M_1, \dots , M_k\) be matroids on a finite set \(E\). Their direct sum \(M_1 \oplus \dots \oplus M_k\) is a matroid on \(\{ 1, \dots , k\} \times E\), in which \(M_j\) lives on the copy \(\{ j\} \times E\) of \(E\).
A bipartite graph matches a set \(I\) of vertices on one side onto a set \(I'\) on the other if some bijection from \(I\) to \(I'\) sends each element of \(I\) to a neighbour. Let \(N\) be a matroid on one side of a bipartite graph, and let \(S\) be the other side. Perfect showed that the subsets of \(S\) that the graph matches onto independent sets of \(N\) are the independent sets of a matroid on \(S\), the matroid induced from \(N\) by the graph [ Oxl11 , Theorem 11.2.12 ] . The union of the \(M_j\) is the matroid on \(E\) induced from their direct sum by the graph that joins each element of \(E\) to its copies. We show that its independent sets are the unions of independent sets of the \(M_j\). Then we prove Rado’s theorem, and from it the rank of the union.
Let \(M_1, \dots , M_k\) be matroids on a finite set \(E\), and let \(\Delta \) be the bipartite graph that joins each \(e \in E\) to its copies \((1, e), \dots , (k, e)\) in the ground set of the direct sum \(M_1 \oplus \dots \oplus M_k\). The union \(\bigcup _j M_j\) is the matroid on \(E\) induced from \(M_1 \oplus \dots \oplus M_k\) by \(\Delta \): a set \(I \subseteq E\) is independent in \(\bigcup _j M_j\) if and only if \(\Delta \) matches \(I\) onto an independent set of \(M_1 \oplus \dots \oplus M_k\). For two matroids we write \(M_1 \cup M_2\).
Nelson’s package proves that a bipartite graph induces a matroid by checking the augmentation axiom. In the formalization the \(M_j\) need not have the same ground set: each is a matroid on a subset of \(E\), and the union is a matroid on all of \(E\). An element of \(E\) outside the ground set of \(M_j\) has no independent copy in the direct sum, so in the union it behaves as a loop of \(M_j\). This is how Oxley defines the union of matroids on different ground sets [ Oxl11 , § 11.3 ] .
Let \(M_1, \dots , M_k\) be matroids on a finite set \(E\). A set \(I \subseteq E\) is independent in \(\bigcup _j M_j\) if and only if \(I = I_1 \cup \dots \cup I_k\) for some sets \(I_j\) independent in \(M_j\).
Let \(I\) be independent in \(\bigcup _j M_j\), so that \(\Delta \) matches \(I\) onto an independent set of the direct sum. The matching sends each \(e \in I\) to a copy \((j(e), e)\). Its image is independent, so each set \(I_j = \{ e \in I : j(e) = j\} \) is independent in \(M_j\), and the union of these sets is \(I\).
Conversely, let \(I = I_1 \cup \dots \cup I_k\) with each \(I_j\) independent in \(M_j\). For each \(e \in I\) choose one index \(j(e)\) with \(e \in I_{j(e)}\). Each set \(\{ e \in I : j(e) = j\} \) is a subset of \(I_j\), so \(e \mapsto (j(e), e)\) matches \(I\) onto an independent set of the direct sum.
The rank of the union rests on Rado’s theorem, which Rado proved in 1942 (see [ Oxl11 , Theorem 11.2.2 ] ). A transversal of a family \((A_i : i \in J)\) of sets is a family \((e_i : i \in J)\) of distinct elements with \(e_i \in A_i\) for every \(i\).
Let \(M\) be a matroid on a set \(S\), and let \((A_i : i \in J)\) be a finite family of finite subsets of \(S\). Then the family has a transversal \((e_i : i \in J)\) such that \(\{ e_i : i \in J\} \) is independent in \(M\) if and only if \(|K| \le r_M\bigl(\bigcup _{i \in K} A_i\bigr)\) for every \(K \subseteq J\).
If such a transversal exists, then for \(K \subseteq J\) the set \(\{ e_i : i \in K\} \) is an independent subset of \(\bigcup _{i \in K} A_i\) with \(|K|\) elements, so the rank of \(\bigcup _{i \in K} A_i\) is at least \(|K|\).
For the converse we follow Oxley, who derives Rado’s theorem from a theorem of Welsh [ Oxl11 , Theorem 11.2.3 ] (Matroid.generalized_halls_marriage). Let \(f\) be a non-negative, integer-valued, non-decreasing submodular function on the subsets of \(S\), and let the sets \(A_i\) be non-empty. Suppose that \(f\bigl(\bigcup _{i \in K} A_i\bigr) \ge |K|\) for every \(K \subseteq J\). Then Welsh’s theorem gives elements \(e_i \in A_i\), not necessarily distinct, with \(f(\{ e_i : i \in K\} ) \ge |K|\) for every \(K \subseteq J\).
We apply it to \(f = r_M\). The sets \(A_i\) are non-empty, since the hypothesis at \(K = \{ i\} \) gives \(r_M(A_i) \ge 1\). For \(i \ne i'\), the case \(K = \{ i, i'\} \) gives \(r_M(\{ e_i, e_{i'}\} ) \ge 2\), so \(e_i \ne e_{i'}\). The case \(K = J\) then shows that the \(|J|\) elements \(e_i\) form an independent set.
Let \(M_1, \dots , M_k\) be matroids on a finite set \(E\), with rank functions \(r_1, \dots , r_k\), and let \(X \subseteq E\). Then the rank of \(X\) in \(\bigcup _j M_j\) is
In particular, \(X\) is independent in \(\bigcup _j M_j\) if and only if \(|Y| \le \sum _j r_j(Y)\) for every \(Y \subseteq X\).
Let \(\Delta \) be as in definition 15.6. The neighbours in \(\Delta \) of a set \(Y \subseteq E\) form the set \(\{ 1, \dots , k\} \times Y\), whose rank in the direct sum is \(f(Y) = \sum _j r_j(Y)\). As a sum of matroid rank functions, \(f\) is a polymatroid rank function (definition 15.2).
We show that \(\bigcup _j M_j\) is the matroid \(M_f\) (definition 15.4; Matroid.polymatroid_of_adjMap). Let \(I \subseteq E\), and apply Rado’s theorem (lemma 15.9) to the direct sum and the family of the sets \(\{ 1, \dots , k\} \times \{ e\} \) for \(e \in I\). A transversal of this family that is independent in the direct sum is a matching of \(I\) onto an independent set. The condition of Rado’s theorem says that \(|Y| \le f(Y)\) for every \(Y \subseteq I\). So \(I\) is independent in \(\bigcup _j M_j\) if and only if it is independent in \(M_f\). The polymatroid rank formula (lemma 15.5) now gives the rank of \(X\). This is Oxley’s proof [ Oxl11 , Lemma 11.2.13 and Theorem 11.3.1 ] .
The set \(X\) is independent exactly when its rank is \(|X|\). For \(Y \subseteq X\) we have \(|X \setminus Y| = |X| - |Y|\), so the rank formula gives the independence criterion.
By lemma 15.8, a set is independent in the union of \(k\) copies of a matroid \(M\) exactly when it is the union of \(k\) independent sets of \(M\), which can be taken disjoint. So for \(k\) copies of one matroid the independence criterion is Edmonds’ matroid-partition theorem [ Edm65 , Theorem 1 ] .
Let \(M\) be a matroid on a finite set \(E\), and let \(k\) be a natural number. A set \(X \subseteq E\) is independent in the union of \(k\) copies of \(M\) if and only if \(|Y| \le k\, r_M(Y)\) for every \(Y \subseteq X\).
The set \(X\) is independent exactly when its rank is \(|X|\). By theorem 15.10 with \(M_1 = \dots = M_k = M\), this rank is the minimum of \(|X \setminus Y| + k\, r_M(Y)\) over the sets \(Y \subseteq X\). For such \(Y\) we have \(|X \setminus Y| = |X| - |Y|\), so the minimum is \(|X|\) if and only if \(|Y| \le k\, r_M(Y)\) for every \(Y \subseteq X\).