6
$\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 the rows of $A$ 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$?

Any relevant references would be much appreciated.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

The question has been resolved by Chris Godsil on Maths Overflow. I repost it here for completeness:

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^⊥∩b^⊥$ is a subspace of codimension two that does not contain a column if and only if $0$ is not in the image of $ρ_{a,b}$.

If we identify $V(G)$ with the standard basis for $GF(2)^{m+2}$ then the map that assigns the vector $ρ_{a,b}(ei)$ 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 $ρ_{a,b}(e_i+e_j)≠0$ if $ij∈E(G)$ and so the kernel of $ρ_{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$
1
  • 1
    $\begingroup$ It is considered good practice not to post in parallel on both sites, and at least wait a few days, so the discussion threads don't overlap. just FYI $\endgroup$ Jul 14, 2011 at 16:04

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.