Planar Graphs and Skew Binary Spaces

Question

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 would be helpful. Relevant references would be much appreciated.

Answer 1

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.