Grafos planos y espacios binarios inclinados

Question

Dejemos que $G$ sea una triangulación plana en $3m$ bordes y $m+2$ vértices. Sea $A$ sea la matriz binaria obtenida a partir de la matriz de incidencia de $G$ borrando una fila (equivalentemente requerimos las filas de $A$ para formar una base del espacio de cocos de $G$ en $GF(2)$ ).

Mi pregunta es: ¿Qué criterios adicionales criterios adicionales deben asumirse (si los hay) para garantizar que haya una $(m1)$ -subespacio dimensional de $GF(2)^{m+1}$ que no contiene ninguna columna de $A$ ?

Es fácil ver que no hay $7$ son las palabras no nulas de un $3$ -El subespacio de las dimensiones, por lo que no se bloquea trivialmente.

Por otro lado, hay ejemplos de $3m$ longitud $m+1$ palabras, que no surgen de un gráfico plano, que no contienen los puntos no nulos de un $3$ -y que bloquean cada $(m-1)$ -subespacio dimensional. (Por ejemplo, considere el conjunto de pesos $2$ palabras en $GF(2)^5$ junto con $10000$ y $01000$ - correspondiente a $K_5$ con un vértice adicional adyacente a exactamente dos vértices de $K_5$ .)

Cualquier límite conocido sobre el tamaño de un conjunto sesgado de este tipo que no sea el de Bose y Burton sería útil. Se agradecerían mucho las referencias pertinentes.

Answer 1

Lo que sigue es bastante estándar, creo que está en el libro de Aigner "Combinatoria" pero mi copia está en préstamo ....

Dejemos que $B$ sea la matriz de incidencia de vértices y aristas del grafo. (No se gana nada borrando una fila.) Queremos un subespacio de codimensión dos en $GF(2)^{m+2}$ que no contiene ninguna columna de $B$ . Si $a$ y $b$ son vectores distintos no nulos vectores indexados por los vértices de $G$ y $x$ es una columna de $B$ tenemos un mapa $\rho_{a,b}$ que envía $x$ a $(a^Tx,b^Tx)$ y $a^\perp\cap b^\perp$ es un subespacio de codimensión dos que no contiene una columna si y sólo si $0$ no es a imagen y semejanza de $\rho_{a,b}$ .

Si identificamos $V(G)$ con la base estándar de $GF(2)^{m+2}$ entonces el mapa que asigna el vector $\rho_{a,b}(e_i)$ al vértice $i$ es una coloración propia de 4 de los vértices de $G$ como puede comprobar fácilmente. Por lo tanto, una condición necesaria es que $G$ ser 4-colorables.

Por otro lado, si $G$ es de 4 colores, entonces podemos colorearlo con los cuatro elementos de $GF(2)^2$ . Sea $a$ sea el vector tal que $a_i$ es la primera coordenada de la coloración del vértice $i$ y que $b$ sea el vector tal que $b_i$ es la segunda coordenada. El $\rho_{a,b}(e_i+e_j)\ne0$ si $ij\in E(G)$ y así el núcleo de $\rho_{a,b}$ es un subespacio de codimensión dos que no contiene una columna de $B$ . (Si $a=b$ tenemos un 2-color, lo cual es imposible).

Así que tu pregunta es equivalente al teorema de los 4 colores.