Let $G$ be a planar triangulation on $3m$ edges and $m+2$ vertices. Let $A$ be the binary matrix obtained from the incidence matrix of $G$ by deleting a row (equivalently we require the rows of $A$ to form a basis of the cocycle space of $G$ over $GF(2)$).



> 
> My question is: What additional
>  criteria must be assumed (if any) to
>  guarantee there is an
>  $(m−1)$-dimensional subspace of
>  $GF(2)^{m+1}$ which does not contain
>  any column of $A$?
> 
> 
> 


It is easy to see that no $7$ columns are the nonzero words of a $3$-dimensional subspace, so it is not trivially blocked.


On the other hand, there are examples of $3m$ length $m+1$ words, not arising from a planar graph, which do not contain the nonzero points of a $3$-dimensional subspace and which block every $(m-1)$-dimensional subspace. 
(For example consider the set of weight $2$ words in $GF(2)^5$ along with $10000$ and $01000$ - corresponding to $K\_5$ with an additional vertex adjacent to exactly two vertices of $K\_5$.)


Any known bounds on the size of a skew set of this type other than that of [Bose and Burton](http://www.sciencedirect.com/science/article/pii/S0021980066800078)  would be helpful. Relevant references would be much appreciated.



Planar Graphs and Skew Binary Spaces
What follows is all quite standard, iirc it's in Aigner's book "Combinatorics" but
my copy's out on loan....


Let $B$ be the vertex-edge incidence matrix of the graph. 
(Nothing's gained by deleting a row.) We want a subspace of 
codimension two in $GF(2)^{m+2}$ containing no column of $B$. 
If $a$ and $b$ are distinct non-zero
vectors indexed by the vertices of $G$ and $x$ is a column of $B$, we have a map 
$\rho\_{a,b}$ that sends $x$ to $(a^Tx,b^Tx)$ and $a^\perp\cap b^\perp$
is a subspace of codimension two that does not contain a column if and only if
$0$ is not in the image of $\rho\_{a,b}$.


If we identify $V(G)$ with the standard basis for $GF(2)^{m+2}$ then the map
that assigns the vector $\rho\_{a,b}(e\_i)$ to the vertex $i$ is a proper 4-colouring
of the vertices of $G$, as you can easily check. Hence a necessary condition is that 
$G$ be 4-colourable.


On the other hand, if $G$ is 4-colourable then we can colour it with the four
elements of $GF(2)^2$. Let $a$ be the vector such that $a\_i$ is the first coordinate
of the colouring of the vertex $i$ and let $b$ be the vector such that $b\_i$ is the 
second coordinate. The $\rho\_{a,b}(e\_i+e\_j)\ne0$ if $ij\in E(G)$ and so the kernel
of $\rho\_{a,b}$ is a subspace of codimension two that does not contain a column of $B$.
(If $a=b$ we have a 2-colouring, which is impossible.)


So your question is equivalent to the 4-color theorem.


