9
$\begingroup$

Let $V$ be a multiset of $kn$ nonzero vectors in $\mathbf{R}^n$. Suppose that for $1 \leq d \leq n$, each $d$-dimensional subspace of $\mathbf{R}^n$ contains at most $kd$ members of $V$. Then $V$ can be partitioned into $k$ bases of $\mathbf{R}^n$.

A proof or a reference would be appreciated.

$\endgroup$
3
  • 2
    $\begingroup$ You probably want to look up the matroid partitioning theorems of Edmonds. $\endgroup$
    – Andy B
    Sep 20, 2011 at 21:51
  • 2
    $\begingroup$ @Andy B, why not write that as an answer? Here's a link to a reprint of one of Edmonds's papers with an introduction by Edmonds: iasi.cnr.it/jack/material/(06)_Matroid_Partitioning.pdf see the discussion on page 210(338 of the original scan). $\endgroup$
    – j.c.
    Sep 20, 2011 at 22:17
  • $\begingroup$ See also books.google.com/… $\endgroup$
    – j.c.
    Sep 20, 2011 at 22:24

1 Answer 1

5
$\begingroup$

Apparently the question was answered in the comments: Edmonds proves a more general theorem for a family of matroids. If the matroids are all the same and if that matroid is a vector matroid, then it is exactly the question stated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.