2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.