This question may be very trivial, I apologize if it is so.


I have subspace $V\subset \mathbb Z\_2^r$ with the property that for every choice of a subset $I$ of $k$ elements in $\{1,2,\dots r\}$, the projection of $V$ onto the corresponding $k$ coordinates is surjective. 


QUESTION: Can one find a lower bound on $\dim V$, apart from the obvious $\dim V\ge k$? 


In the case I'm interested in I have $k\ge \frac r 2$. 



Lower bound on the dimension of a subspace of $\mathbb Z_2^r$? 
Let $\pi\_i:V\to\mathbb Z\_2$ be the projection to the $i$-th coordinate. The $\pi\_i$ are elements of the dual space $V^\star$, and by assumption, any $k$ of these $\pi\_i$ are linearly independent. Let $C$ be subspace of $\mathbb Z\_2^r$ consisting of those tuples $(a\_1,\dots,a\_r)$ such that $\sum a\_i\pi\_i=0$. So $C$ is a code of minimal Hamming distance $d\ge k$. On the other hand, $\dim C=r-\dim\langle\pi\_i|i=1,2,\dots,r\rangle\ge r-\dim V^\star=r-\dim V$.


Thus $\dim V\ge r-\dim C$. Now use some good bounds from error correcting codes. If $k$ is bigger than $r/2$, then the Plotkin bound gives good results, here $2^{\dim C}\le k/(k-r/2)$, which is much better than $\dim V\ge k$.


If $k=r/2$, or $k\lt r/2$ then one can use the Griesmer bound, or other bounds if $k$ is small compared to $r$.


