Let $M$ be a matroid over ground set $S$ and $k$ and $\ell$ be non-negative integers such that $k\geq \ell$. We consider the following problem.

**Problem 1.** Find a partition of $S$ into $k$ parts such that the union of any $\ell$ of them forms

(a) an independent set of $M$,

(b) a basis of $M$,

(c) a spanning set of $M$.

Note that Problems 1(a) and 1(c) are closely related as a set $I\subseteq S$ is independent in $M$ if and only if $S-I$ is a spanning set in the dual matroid $M^*$. That is, a solution for an instance $M$, $k$ and $\ell$ of Problem 1(a) provides a solution for the instance $M^*$, $k$, $k-\ell$ of Problem 1(c), and vice versa.

Edmonds and Fulkerson [1] solved the problem of packing bases in a matroid, or more generally, packing bases of $k$ matroids in a pairwise disjoint way. Using their result, the cases $\ell=1$, $\ell=k-1$ and $\ell=k$ can be solved efficiently for all three of the problems.

**References**

[1] J. Edmonds and D. R. Fulkerson, Transversals and matroid partition, Journal of Research of the National Bureau of Standards (B), 69:147–153 (1965).