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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You probably want to look up the matroid partitioning theorems of Edmonds. $\endgroup$
    – Andy B
    Commented 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.
    Commented Sep 20, 2011 at 22:17
  • $\begingroup$ See also books.google.com/… $\endgroup$
    – j.c.
    Commented Sep 20, 2011 at 22:24

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .