Publicado por Miguel Rubio
En 1850 Francis Guthrie, un estudiante de leyes inglés, se entretenía tratando de colorear el mapa de Inglaterra utilizando la menor cantidad de colores posibles. Tenía la intuición de que se podía hacer con sólo 4 colores,pero no pudo conseguirlo.
Francis le comentó el tema a su hermano Frederick, que a su vez se lo planteó a su profesor Augustus de Morgan (un prestigioso matemático nacido en la india, profesor de matemática en el University College de londres), que no pudo resolverlo, pero se encargo de difundir el asunto entre otros matemáticos.
En 1878 Arthur Cayley lo presenta formalmente a la London Mathematical Society y el problema queda abierto con un enunciado similar al siguiente:
«Todo mapa plano puede colorearse con, como máximo, cuatro colores con la condición de que regiones con frontera común tengan colores distintos.»
Al poco tiempo Alfred Kempe propuso una demostración que publicó en 1879 en la revista Nature. Al año siguiente publicó una versión simplificada en los Proceedings of the London Mathematical Society, corrigiendo algunas erratas de su prueba original. En 1890, Percy John Heawood encontró un error en la demostración de Kempe. Heawood siguió trabajando en el problema pero no lo solucionó, sin embargo consiguió probar que con cinco colores si se podía colorear cualquier mapa.
Arthur Cayley 
Alfred Kempe 
Percy John Heawood
Frederick Guthrie fue el primero en observar que el problema de los cuatro colores no se podía generalizar a dimensión 3, ya que es posible construir un ejemplo de mapa tridimensional que precise tantos colores como se desee. Basta con colocar una barra horizontal por cada color, una a continuación de otra, y luego colocar encima de ellas, pero en forma perpendicular, de nuevo una barra de cada color también una a continuación de otra. De esta forma, siempre habrá dos regiones adyacentes con el mismo color, y esto es válido para cualquier cantidad de colores que se considere siempre que las barras sean lo suficientemente largas.
El propio Francis Guthrie demostró que tres colores no son suficientes para colorear cualquier mapa que se presente. Basta considerar la figura a la izquierda. El lector que desee comprobarlo, puede intentar colorear esta figura con tres colores.
El hecho de que la figura sea circular no es importante, ya que se trata de un problema eminentemente topológico (las distancias y las formas son irrelevantes).
En efecto, fue a través de la teoría de grafos como los matemáticos abordaron el problema. una breve introducción a la teoría de grafos se puede ver aquí.
La coloración de grafos es una asignación de etiquetas llamadas colores a los elementos del grafo. Una coloración de los vértices de un grafo tal que dos vértices con una arista en común nunca compartan el mismo color es llamado vértice coloración.
En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloración depende del número de colores pero no de cuales son esos colores.
La coloración de mapas es un problema que se traduce matemáticamente en forma directa en un problema de coloración de grafos: cuál es la cantidad mínima de colores necesarios para colorear los vértices de un grafo plano de modo que dos vértices adyacentes no tengan el mismo color ?
La forma precisa de cada región del mapa no importa; lo importante es saber qué región toca a qué otra región. Estos datos están incluidos en el grafo donde los vértices son las regiones y las aristas conectan las que son adyacentes, es decir, que tienen una frontera común (no se consideran adyacentes las regiones que sólo tengan un punto en común). Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos.
Claro que estamos hablando de un mapa dibujado en un plano.
Que pasa si el mapa lo dibujamos sobre otra superficie?
En el caso de un globo terráqueo el mapa estaría dibujado sobre una esfera. El número mínimo de colores será el mismo?
Este tipo de consideraciones llevó a los matemáticos a definir un número que se asocia a cada grafo y a cada tipo de superficie denominado índice cromático de la superficie, y para cada grafo número cromático del grafo. El problema original de Guthrie consiste entonces en encontrar el índice cromático del plano, o lo que es equivalente, el número cromático de los grafos planos.
Un resultado un poco más general de la teoría de grafos establece que si un grafo plano tiene como máximo tres triángulos, entonces su número cromático es tres, es decir, se puede encontrar una vértice coloración de tres colores.
Qué pasa con otras superficies?
Ahora, construyamos un toro coloreándolo de la siguiente forma:
Está claro que son necesarios al menos 7 colores.
En efecto, el índice cromático del toro es 7, es decir, un mapa dibujado sobre el toro necesita cuanto más 7 colores.
En una cinta de Möbius bastan con 6 colores para colorear cualquier mapa.
Y en el caso de la esfera?
En ese caso, un teorema de la teoría de grafos establece que cualquier grafo dibujado sobre la esfera, es un grafo plano, con lo cual colorear un mapa plano es lo mismo que colorear dicho mapa sobre un globo terráqueo.
A esta altura es conveniente dejar clara la terminología que utilizamos: cualquier grafo se puede dibujar en el plano.
Cuando decimos que un grafo es plano, nos referimos a que lo podemos dibujar en el plano sin que sus aristas se crucen entre sí.
El lector puede comprobar que es imposible dibujar los grafos de la figura a la izquierda sin que se crucen sus aristas.
Análogas consideraciones cuando hablamos de dibujar un grafo sobre otra superficie.
En 1912, el matemático estadounidense George David Birkhoff introduce la idea del polinomio cromático. A pesar de que a la larga este método no fue efectivo para resolver el problema de los cuatro colores, el polinomio por sí mismo se convirtió en un importante objeto de estudio en teoría algebraica de grafos. A mediados del siglo XX, a pesar de los avances que se hicieron, se comenzó a pensar en el uso de ordenadores para atacar este problema. El matemático alemán Heinrich Heesch, quien había realizado importantes aportes en el estudio de las teselaciones del plano (resolvió en 1932 uno de los 23 problemas de Hilbert de 1900), realizó un trabajo pionero en el desarrollo de métodos para una prueba asistida por computadora del teorema de los cuatro colores.
George Birkhoff
Heinrich Heesch
Fué el primero en estudiar la noción de «descarga», un concepto que resultó fundamental para abordar el problema a través de un ordenador. La idea intuitiva que subyace a la descarga consiste en considerar el grafo plano como una red eléctrica: la carga eléctrica, inicialmente positiva y negativa se distribuye entre los vértices . Luego, la carga se redistribuye sistemáticamente de un vértice a sus vértices vecinos de acuerdo con un conjunto de reglas (el procedimiento de descarga ).
Aunque tuviera un error, la prueba original de Kempe proporcionó algunas de las herramientas básicas que más tarde se usaron para demostrarlo: si las regiones planas separadas por el grafo no son triangulares, podemos agregar aristas sin introducir nuevos vértices para hacer que cada región sea triangular, incluida la región exterior sin límites.
Si este grafo triangulado se puede colorear con cuatro colores o menos, lo mismo sucede con el grafo original, ya que la misma coloración es válida si se eliminan las aristas. Esto significa que sólo hay que demostrar el teorema para grafos triangulares. Si de un conjunto de configuraciones (una configuración es un ciclo con vértices internos triangulados) por lo menos una de ellas debe ocurrir en algún lugar del grafo, ese conjunto se llama inevitable:
El método principal utilizado para descubrir dicho conjunto inevitable es el procedimiento de descarga de Heinrich Heesch.
En 1969, Heinrich Heesch sistematiza la prueba de la reducibilidad, desarrollando un algoritmo que intenta implementar con ordenador con su alumno Wolfgang Haken. Realiza diversos tests con el programa Algol 60 y afirma que la conjetura puede resolverse considerando tan sólo 8.900 configuraciones. Luego elabora una manera de construir conjuntos inevitables a través de su algoritmo de descarga. En 1976 el teorema fue demostrado por Kenneth Appel y Wolfgang Haken, que utilizaron un ordenador para probar que sus 1.482 configuraciones son reducibles, lo cual demandó 50 días de cálculo. Esto generó múltiples controversias en el ambiente matemático.
Wolfgang Haken nació el 21 de junio de 1928 en Berlín , Alemania.En 1962, dejó Alemania para convertirse en profesor visitante en la Universidad de Illinois en Urbana-Champaign donde Se convirtió en profesor titular en 1965.
Gran parte de su trabajo tiene un aspecto algorítmico, siendo uno de los referentes de la topología algorítmica (la topología algorítmica, desarrolla algoritmos eficientes para resolver problemas que surgen naturalmente en campos como la geometría computacional , la teoría de grafos , robótica , biología estructural y química , utilizando métodos de topología computable, que estudia la estructura topológica y algebraica de la computación).
Sus principales contribuciones a este campo son un algoritmos relacionados con la teoría de nudos.
Kenneth Appel nació en Brooklyn, Nueva York , el 8 de octubre de 1932, y murió en Dover, New Hampshire , el 19 de abril de 2013. En 1961 ingreso en la facultad del Departamento de Matemáticas en la Universidad de Illinois como profesor asistente, en 1967 se convirtió en profesor asociado y en 1977 fue ascendido a profesor.
Hizo importantes aportaciones a la teoría de grupos: Appel y Schupp introdujeron cuatro teoremas que son verdaderos sobre los grupos de Coxeter y luego demostraron que son ciertos para los grupos de Artin.
Presidió el departamento de matemáticas de la Universidad de New Hampshire de 1993 a 2002, y se retiró como profesor emérito en 2003.
El teorema de los cuatro colores se ha caracterizado por tener una gran cantidad de pruebas falsas y refutaciones en su larga historia. Al principio, The New York Times se negó a informar sobre las pruebas de Appel-Haken, temiendo que las pruebas se mostraran falsas como las anteriores, ya que algunas supuestas pruebas, como la de Kempe mencionada anteriormente, demoraron más de una década en ser refutadas, pero muchas más demostraciones escritos por aficionados, nunca se publicaron en absoluto.
Finalmente, el New York Times publicó:
«Ahora, la conjetura de cuatro colores ha sido probada por dos matemáticos de la Universidad de Illinois, Kenneth Appel y Wolfgang Haken . Tenían una herramienta invaluable de la que carecían los matemáticos anteriores: las computadoras modernas. Su prueba actual se basa en parte en 1.200 horas de cálculo computarizado durante las cuales se tuvieron que tomar cerca de diez mil millones de decisiones lógicas. La prueba de la conjetura de cuatro colores es poco probable que tenga importancia aplicada. Sin embargo, lo que se ha logrado es una gran hazaña intelectual. Nos proporciona una nueva e importante visión de la naturaleza del espacio bidimensional y de las formas en que dicho espacio se puede dividir en partes discretas.»
La prueba de Appel y Haken ha sido una de las más controvertidas debido a su gran dependencia de la computación numérica para analizar las posibilidades, lo que atrajo críticas de muchos en la comunidad matemática por su falta de elegancia. Appel y Haken acordaron en una entrevista de 1977 que no era «elegante, concisa y completamente comprensible para una mente matemática humana». Fue el comienzo de un cambio en las actitudes de los matemáticos hacia las computadoras hasta el punto que llevó a la creación de lo que se conoce como matemática experimental (La matemática experimental es un enfoque de la matemática en el que el cálculo se utiliza para investigar objetos matemáticos e identificar propiedades y patrones asociados a los mismos).
Martin Gardner nació en Estados Unidos, el 21 de octubre de 1914. Estudió Filosofía y después comenzó su carrera de periodista y escritor. Escribió durante 25 años una columna mensual en la revista Scientific American llamada Juegos Matemáticos. Fué autor de más de 70 libros, principalmente dedicados a la matemática recreativa. Falleció el 22 de mayo de 2010 a la edad de 95 años.
Publicó el 1 de abril de 1975 (el día de los inocentes para los anglosajones) un mapa plano de 110 regiones construído en noviembre de 1974 por William McGregor especialista en teoría de grafos, donde lo presentaba como un contraejemplo que demostraba la falsedad del teorema de los 4 colores. Vaya broma que les gastó a los ingleses. Es destacable que los lectores en general no se percataran de que se trataba de una broma. En este artículo Gardner anunciaba «hechos» como la refutación de la teoría de la relatividad de Einstein, a través de un experimento del físico británico Humbert Pringl o la construcción (debida al parapsicólogo Robert Ripoff) de un motor funcionando con energía mental.
Martin Gardner 
Mapa de McGregor
El caso es que Gardner recibió una infinidad de cartas con el mapa coloreado con 4 colores.
Posteriormente a la demostración del teorema de los cuatro colores con ayuda de ordenadores, otras demostraciones utilizaron este método: por ejemplo la clasificación de los grupos simples finitos (2004) o la solución de Thomas Hales (1998) del problema de Kepler sobre el empaquetamiento óptimo de esferas. Se supone que una demostración debe ser convincente, formalizable y comprobable, y es en este último requerimiento donde surge la controversia: una persona debe verificar la demostración, pero ni siquiera se puede leer en su totalidad.
El matemático belga Pierre Deligne opina:
“No creo en una prueba hecha con ordenador. En primer lugar, soy demasiado egocéntrico. Creo en una demostración si la entiendo, si está clara. Un ordenador puede también cometer errores, pero es mucho más difícil encontrarlos”.
También Paul Richard Halmos, destacado matemático estadounidense, nacido en Budapest (Hungría) se mostró escéptico:
“No puedo aprender nada de la demostración. La prueba no indica la razón por la que sólo se necesitan 4 colores ¿por qué no 13? ¿Qué tiene de especial el número 4?”.
Pierre Deligne 
Paul Richard Halmos
Por otro lado, quienes aceptan este tipo de demostraciones argumentan que los ordenadores siguen un programa rígido predeterminado, y no tienen tropiezos motivados por los cambios de humor, el estrés u otros factores externos; además la idea de que no pueden usarse ordenadores va a ser cada vez más insólita para las generaciones futuras: los ordenadores son hoy en día herramientas como el lápiz y el papel. Además la prueba de Appel y Haken es tradicional: consiste en una serie de pasos lógicos, que reducen la conjetura a una predicción sobre el comportamiento de unos 2.000 mapas.
La discusión está servida.
El caso es que en 1977 se imprimió un matasellos con la inscripción «cuatro colores son suficientes»:
En 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour y Robin Thomas (de la Escuela de Matemáticas del Georgia Institute of Technology), publicaron una nueva demostración basados en la demostración de Appel y Haken pero con solo 633 configuraciones y 32 reglas de descarga.
Por último un pasatiempo para los lectores, publicado por el diario El País del 9 de agosto de 1998:
2 comentarios
[…] por Ian Stewart con un capítulo que incluye descripciones del análisis no estándar, de la demostración del teorema de los cuatro colores y de la demostración del último teorema de […]
[…] Ya he mencionado en un artículo anterior cómo Leonhard Paul Euler creó la teoría de grafos: “El trabajo de Leonhard Euler sobre el problema titulado La solución de un problema relativo a la geometría de la posición , es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría.” Por ejemplo, dicha teoría es la que permitió demostrar el teorema de los cuatro colores: […]