What is the maximum value $m$ such that an unordered set of $n + m$ vectors spans $\mathbb{F}^n_2$ when any $m$ vectors are excluded?
Also, is there an efficient method for generating such a sequence for a given $m$ (assuming there exists at least one value of $n$ where $m > 1$; see trivial expansion below)?
By exhaustive search here's the only example of $m = 1$ for $\mathbb{F}^2_2$: $$v_1 = (1, 0)$$ $$v_2 = (0, 1)$$ $$v_3 = (1, 1)$$
Here's an example of $m = 1$ for $\mathbb{F}^3_2$: $$v_1 = (1, 0, 0)$$ $$v_2 = (0, 1, 0)$$ $$v_3 = (0, 0, 1)$$ $$v_4 = (1, 1, 1)$$
I'm unable to find an $m > 1$ for $n = 3$; neither am I able to find another example of $m = 1$. But $m = 1$ can trivially be expanded to any $n$ by following the pattern of $n$ rows of the identity matrix $I_n$ followed by a vector of all $1$'s. So $ \forall n : m \geq 1$. Also, there are only $2^n$ vectors in $\mathbb{F}^n_2$ and one of those is the zero vector, so $n + m < 2^n$. But those are some pretty loose bounds.
Here's nearly an example of $m = 2$ for $\mathbb{F}^3_2$. But $\{v_1, v_2, v_4\}$ doesn't span $\mathbb{F}^3_2$; neither does $\{v_1, v_3, v_5\}$. But I think the other $((n + m) \text{ choose } n) - 2 = 8$ linear combinations span $\mathbb{F}^3_2$: $$v_1 = (1, 1, 1)$$ $$v_2 = (0, 1, 1)$$ $$v_3 = (0, 0, 1)$$ $$v_4 = (1, 0, 0)$$ $$v_5 = (1, 1, 0)$$
It seems that $\forall{k} : \sum{v_{i}(k)} \geq m + 1$ or else you could just take out the $m$ vectors that have $1$ in their $k^\text{th}$ spot and then you wouldn't be able to make linear combinations of the $k^\text{th}$ dimension. But I'm having a tough time turning that into a bounds for $m$.
$m=1$ for all $n$. If you have at least $n+2$ vectors, express any two vectors $u,v$ as a linear combination of the other $n$. (If you can't, those $n$ don't span the space.) At most one of $u,v$ can have all coefficients $1$, the other, say, $u$, must have at least one coefficient $0$, so we don't need the corresponding vector; remove it and $v$, leaving a linearly dependent set of $n$ vectors.
(This explains why in each of your examples for $m=1$ each vector is the sum of the others.)