Historia del problema de los cuatro colores

Algunos de los problemas más famosos de las matemáticas surgen a partir de preguntas muy sencillas. El 23 de octubre de 1852, De Morgan escribía a Hamilton:

“Un estudiante me pidió que le diera un argumento sobre un hecho que yo ni siquiera sabía que era un hecho, ni lo sé aún ahora. El estudiante dice que si uno toma una figura (plana) cualquiera y la divide en compartimentos pintados con diferentes colores, de manera tal que dos adyacentes no tengan un color en común, entonces él sostiene que cuatro colores son suficientes”.

Había nacido el problema de los cuatro colores: probar que, dado un mapa cualquiera en el plano, cuatro colores bastaban para colorearlo de manera que países vecinos lleven colores distintos. Es un problema de enunciado sencillo y apariencia inofensiva, pero que se esconde numerosas sutilezas.

Su (agitada) historia

El estudiante al que se refería de Morgan era Frederick Guthrie (que acabaría dedicándose a la física y a la poesía), que le transmitía una observación hecha por su hermano menor, Francis (luego abogado, matemático y botanista), mientras se afanaba en colorear un mapa de Inglaterra. De Morgan, vivamente interesado por el problema, escribió inmediatamente a Hamilton pidiéndole su opinión. Preocupado por si la cuestión resultaba ser trivial, se justificaba (con cierta rotundidad): '

Carta de De Morgan a Hamilton, 1852

Cuanto más pienso sobre ello, más evidente me parece. Pero si usted me muestra algún caso sencillo que me haga quedar como un animal estúpido...

Son las desventajas de plantear preguntas tan aparentemente sencillas. La cuestión no pareció interesar especialmente a Hamilton, que le contestaría no es probable que pueda atender a su problema de los cuatro colores en un futuro próximo...

En 1879, Kempe (otro abogado y matemático) publicó una demostración del teorema de los cuatro colores CT4C), que parecía dar fin al joven problema. Hasta que Heawood, en 1890, mostró que la prueba de Kempe no era correcta (aunque sí bastaba para probar que cinco colores son suficientes).

No fue hasta 1976 cuando Appel y Haken (con la ayuda de Koch) publicaron, finalmente, la prueba completa del teorema

¿Y es realmente interesante?

Limitar el número de colores utilizados al confeccionar un mapa no parece especialmente relevante. 

Pero, aparte de razones psicológicas (una pregunta tan sencilla deviene en un magnífico desafío matemático), existen otras que justifican el interés del P4C: como en otros muchos problemas matemáticos clásicos, los métodos desarrollados para resolverlo han resultado ser, al menos, tan interesantes como el problema original.

El número mínimo de colores necesario para colorear un grafo G es su número cromático, X(G); y lo que afirma el T4C es que X(G) ≤ 4 para cualquier grafo G plano.

Pero calcular X(G) es un problema de optimización: buscamos la mejor manera de colorear.

Hay multitud de problemas interesantes que pueden ser descritos con el lenguaje de los grafos y los colores. Pensemos en la confección de horarios: tenemos una serie de asignaturas a las que queremos asignar horarios para ser impartidas.

Lo queremos hacer de manera que asignaturas que compartan alumnos no sean programadas a la misma hora. Podemos describir la información relevante con un grafo: las asignaturas son los vértices y las incompatibilidades, las aristas. Las distintas horas de que disponemos son los colores, y confeccionar un horario no es sino dar una coloración del grafo. Optimizar este proceso (colorear el grafo con el mínimo número de colores posible) debería ser nuestro objetivo.

Es uno de los teoremas más famosos dentro de la Teoría de Grafos,  fue el primer teorema que
se demostró usando ordenadores y que, por lo tanto, sirvió una gran polémica al respecto.

¿Está probado o no el T4C?

La demostración de Appel y Haken resultó polémica desde el primer momento.

Especialmente, porque requería un uso abundante del ordenador para verificar la inevitabilidad (y la reducibilidad) del conjunto de 1476 configuraciones a las que reducían el problema. En realidad, una objeción todavía mayor que se podía plantear a esta demostración es que la parte de matemáticas tradicionales tampoco era fácil de verificar. 

En 1996 se propuso una prueba alternativa que resulta más legible. Pero, a pesar de reducir a 633 el número de configuraciones, sigue requiriendo el uso del ordenador para su comprobación.

En 1998, Hales anunció la prueba de otro problema clásico, el problema de Kepler: ¿cuál es la manera más eficiente de apilar esferas en el espacio? La conjetura afirmaba que la mejor forma de hacerlo es la que cualquiera seguiría al apilar naranjas en una caja. Este problema tiene bastantes similitudes con el P4C: ambos tienen planteamientos sencillos, han conocido muchos intentos infructuosos por resolverlos, han dado lugar a técnicas matemáticas interesantes... y la demostración final requiere el uso del ordenador para verificar un conjunto finito de configuraciones.

Y la pregunta, por supuesto, es si una demostración de esas características es aceptable. Tanto en el T4C como en el problema de Kepler, cualquiera puede verificar la corrección del programa que realiza los cálculos (o diseñar el suyo propio).

Y estos programas se han compilado y ejecutado en distintos ordenadores y plataformas.

Aun así, siempre queda la duda, ¿no? Pero dado el espectacular papel que empieza a desempeñar el ordenador en estos menesteres... quizás es hora de cambiar nuestra concepción tradicional de demostración matemática.

El problema de los cuatro colores.
fue probado por Appel y Haken (1976)https://t.co/vM7e1mjwKj#Nota140 pic.twitter.com/nVvDXqUllZ

— Jamessi (@jamessi_) 21 de junio de 2016

Fuentes para profundizar

La imagen es de la profesora Clara Grima, en sus "Mati y sus aventuras" 
Titulado: Dame 4 colores y pintaré el mundo.