Prueba algebraica del teorema de cinco colores usando polinomios cromáticos por Birkhoff y Lewis en 1946

Question

Supongo que todo el mundo está familiarizado con el Teorema de los Cuatro Colores , que fue demostrado por Appel y Haken el uso de computadoras. Una versión más débil de este teorema es de Cinco Colores Teorema que dice que un grafo es planar de 5 engañosa. Es bastante simple para probar Cinco Colores Teorema en un estándar de la aproximación matemática (sin recurrir a las computadoras) y muchos teoría de grafos libros de texto explican esta prueba basado en la inducción. (Incluso la wikipedia el artículo cubre la prueba.)

Ahora, estoy interesado en una prueba algebraica de Cinco Colores Teorema usando cromática polinomios. Deje $\pi_G(x)$ ser un chromataic polinomio de un gráfico de $G$. Los Cinco Colores Teorema queda demostrado una vez $\pi_G(5) > 0$ se muestra para cualquier plano gráfico de $G$ porque $\pi_G(5)$ es el número de la 5-el color de un gráfico de $G$. De hecho, Birkhoff introdujo el polinomio cromático con la esperanza de demostrar el Teorema de los Cuatro Colores mostrando que $\pi_G(4) > 0$ para cualquier plano gráfico. Este enfoque fue en vano, sin embargo, él y Lewis tenido éxito en demostrar que $\pi_G(x) > 0$ para cualquier plano gráfico de $G$ al $x$ es un número real mayor o igual que 5. Para esta prueba algebraica de Cinco Colores Teorema, de muchas personas, punto de 97 páginas de papel escrito por Birkhoff y Lewis en 1946.

---

Como una ciencia de la computación TA de un gráfico avanzado de la teoría del curso, creo que esta prueba algebraica es la pena para una explicación breve y puede ser un buen tema de tesis de maestría del estudiante, o incluso un estudiante de grado. Pero es algo difícil de averiguar qué parte de la página 97 documento se trata de una prueba algebraica de Cinco Colores Teorema. (Esto es probablemente porque yo no soy un hablante nativo y que no están familiarizados con el papel estilos de escritura hace casi 70 años.)

1. Hay alguien que ya ha leído Birkhoff y Lewis y me puede decir en que sección es acerca de el real de la prueba de álgebra?
2. ¿Hay alguna otra últimos apuntes o libros de texto que explican esta prueba algebraica en una concisa?

Answer 1

Traté de ir a través de Birkhoff y Lewis hace muchos años, pero no es fácil, ya que utilizan diferentes variables y el estilo es muy diferente al de los modernos pruebas.

En términos modernos, la idea clave es que si un grafo contiene un vértice $v$ de grado k, entonces usted puede obtener una expresión de la forma $$P(G,\lambda) = (\lambda-k) P(G-v,\lambda) + \text{other terms}$$ donde los otros términos son todos cromática polinomios de menores de $G$.

Así que si la hipótesis inductiva es que $P(G,x)> 0$ para todos los $x\geq 5$, luego esta reducción se da el paso inductivo.

Sabemos que cualquier plano gráfico tiene un vértice de grado en la mayoría de los 5, y que un menor de edad de un plano de grafo es planar, y así está hecho.

La expresión que implique $(\lambda-k)$ fue demostrado por Thomassen, por separado, Woodall, y más generalmente de todos los matroids por Oxley, cuyo resultado precedido por dos décadas. Sin embargo, a pesar de que demostró el resultado, Oxley en realidad no estado de forma explícita, por lo que falta puede ser excusado.

Voy a sacar el BL papel mañana y ver si su enfoque es esencialmente la misma.

Agregó creo que el resultado está contenida en el Teorema 3.1 en la página 413 de la BL papel (disponible gratuitamente en el AMS), que delimita los coeficientes de un polinomio $Q$ (el polinomio cromático después de un par de trivial se eliminan los factores). Ellos amablemente la observación de que en este capítulo, el uso del símbolo $\ll$ es "contrario a la notación del capítulo anterior", presumiblemente para evitar la autocomplacencia por parte del lector.