Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Source. Theorem 2d, printed p. 152 (published PDF).
Statement. With pairwise disjoint independent and as above, pairwise disjoint bases of satisfying exist if and only if
Proof. If such bases exist, is an independent subset of , since it cannot contain any other seed. Hence
Summing inside proves necessity.
For sufficiency, first apply (1) to . Each summand is nonnegative by rank monotonicity, so their sum can be at most zero only if
Thus the rank obstruction must be checked before constructing a packing of full bases.
As in Theorem 1d, contract and restrict to . The resulting matroid has
where the second equality uses (2). Substituting these expressions in Theorem 2c on gives exactly (1). It yields disjoint bases of . Each is independent in and has elements, so is a base. The unions are pairwise disjoint because the lie in and the seeds were disjoint. This proves sufficiency, including and rank zero.