# Partitioning the ground set of a matroid

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  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
 J. Edmonds and D. R. Fulkerson, Transversals and matroid partition, Journal of Research of the National Bureau of Standards (B), 69:147–153 (1965).