Teorema de los cuatro colores

Teorema de los cuatro colores

El teorema de los cuatro colores establece la posibilidad de colorear (también decimos colorear en Teoría de grafos) con cuatro colores solo un mapa geográfico sin dos países vecinos que tengan el mismo color.

Para ser más precisos, el teorema de los cuatro colores establece que al usar solo cuatro colores diferentes, es posible colorear cualquier mapa cortado en regiones relacionadas (en una sola pieza), de modo que dos regiones adyacentes (o limítrofes), es decir, tener un borde completo (y no solo un punto) en común siempre recibe dos colores distintos.
Por lo tanto, a cada una de las regiones se le debe dar un color diferente si las regiones son adyacentes de dos en dos.

Además, no pueden existir cinco regiones adyacentes de dos por dos conectadas (esta es la parte fácil del teorema de Kuratowski).

Este teorema de los cuatro colores tiene una aplicación práctica en la asignación por parte de un operador de telefonía móvil de frecuencias GSM a las áreas de cobertura de las estaciones base de su red. De hecho, como en la situación de los cuatro colores:

- una red GSM se modela, como un mapa geográfico, por hexágonos contiguos: cada hexágono (llamado “celda”, de ahí la noción de red celular) corresponde a la radiación de una estación base (aproximadamente 30 km de diámetro en zona rural).

- en ningún caso se debe asignar la misma banda de frecuencia a dos hexágonos contiguos.

Historia del teorema de los cuatro colores

La primera conjetura de cuatro colores parece haber sido hecha en 1852 por un matemático y botánico sudafricano, Francis Guthrie (1831-1899).

Francis Guthrie era estudiante en el University College London, donde estudió con el famoso De Morgan.
Luego se dedicó a los estudios de botánica, mientras que su hermano, Frederick Guthrie, se convirtió en matemático y también siguió los cursos de De Morgan.
Francis Guthrie advierte que cuatro colores le bastan para colorear el mapa (aunque complejo) de los cantones de Inglaterra, sin dar el mismo color a dos cantones adyacentes (que tienen una frontera común).
Luego le pregunta a su hermano Frederick, si esta propiedad no sería cierta en general para ningún mapa plano; este último comunicó la conjetura a De Morgan, y en 1878 Cayley la publicó.

• Ya en 1879, Kempe encontró una primera "prueba" de la conjetura, pero once años más tarde Heawood encontró una falla importante en ella; sin embargo, logrará encontrar un teorema de cinco colores.
  Una segunda "prueba" de Tait en 1880 también será refutada por Petersen en 1891.
• En 1913, el matemático estadounidense George David BIRKHOFF (1884 - 1944), demostró la conjetura de todos los mapas con menos de 26 regiones a colorear.
  Este terminal se mejora durante el XX^mi siglo.
• En 1969, Heesch encontró condiciones "casi" necesarias y suficientes para que una configuración fuera reducible, y un método general para encontrar un conjunto inevitable de configuraciones.

La primera prueba generada por computadora.

• Finalmente, en 1976, los matemáticos estadounidenses Kenneth Appel (murió el 19 de abril de 2013 a los 80 años) y el matemático alemán Wolfgang Haken llevar a cabo el programa de Heesch.
  Muestran, utilizando decenas de miles de cifras, que cualquier mapa que no tenga 4 colores debe contener una de las 1478 configuraciones y, con 1200 horas de cálculo, que estas configuraciones son reducibles.

  Se hace la primera demostración computarizada de un teorema matemático.

• En 1995, Robertson, Sanders, Seymour y Thomas aprovecharon la formidable aceleración de las computadoras para encontrar una realización mucho más simple del programa de Heesch, con solo 633 configuraciones; además, también automatizan la prueba de inevitabilidad.
• En septiembre de 2012, seis años después de la demostración por computadora del teorema de los cuatro colores, Georges Gonthier y su equipo lograron demostrar el teorema de Feit y thompson. Un teorema aún más difícil de formalizar.