Un aficionado hace el primer avance de los últimos 60 años en un famoso problema de combinatoria

El llamado problema de Hadwinger-Nelson es de esas cuestiones matemáticas muy fáciles de formular y entender, incluso para los no expertos, como el problema del mapa de los cuatro colores o el último teorema de Fermat. Sin embargo, pese a esta aparente sencillez a menudo la solución resulta extraordinariamente sofisticada y requiere unas matemáticas que solo están al alcance de muy pocos expertos. Pese a ello, el autor del primer avance en el problema de Hadwinger-Nelson de los últimos 60 años ha sido un no especialista: Aubrey de Grey, un gerontólogo bastante conocido y mediático, que sostiene que es posible detener el proceso de envejecimiento.

El problema de Hadwiger-Nelson estudia coloraciones del plano. Se trata de dar un color a cada punto del plano de manera que todos los puntos que estén a distancia uno tengan asignado un color diferente. Si se quiere pintar de esta manera un plano, todo lo grande que queramos, ¿cuál es el menor número de colores necesarios? El problema fue planteado en 1950 por Edward Nelson, aunque algunos resultados relacionados ya aparecieron en un artículo de Hugo Hadwiger de 1945. Hasta hace poco, se sabía que la respuesta podía ser cuatro, cinco, seis o siete.

Efectivamente, no puede ser más de siete. Con solo siete colores se puede colorear el plano a partir de una teselación de hexágonos de diagonal ligeramente inferior a uno, en la que todos los polígonos adyacentes tengan un color diferente. Partimos de uno de los hexágonos y lo pintamos de un color, y los seis adyacentes de otros seis colores diferentes (y así sucesivamente). Si dos puntos están a distancia uno, caerán en hexágonos distintos de distinto color" (no necesariamente adyacentes)..

Está claro entonces que siete es la cota máxima para el problema, pero, ¿hay una mínima? Para ver que ha de ser al menos cuatro, bastaría con encontrar una configuración de cuatro puntos que estén todos a distancia uno del resto (que, por tanto, no podrían colorearse con solo tres colores). Pero el caso es que no existe: cuatro puntos que disten todos uno entre sí forman los vértices de un tetraedro regular, cuyos vértices no están sobre el mismo plano. Sin embargo, son conocidas algunas configuraciones de puntos que necesitan cuatro colores (es imposible hacerlo con tres). Así sucede como los siete puntos del llamado “huso de Moser” que son los señalados en la siguiente imagen:

En 1961 los hermanos William y Leo Moser dieron esa configuración, y desde entonces no se había avanzado nada en el problema. Ahora Aubrey de Grey ha dado una configuración de puntos tales que necesitan al menos cinco colores para ser coloreados, es imposible hacerlo con cuatro. Aunque el ejemplo dado por Grey contiene 1581 puntos, el método para construirlo es descriptivo y no es excesivamente complicado. En los últimos días se ha conseguido rebajar la configuración hasta los 633 vértices, a través de un proyecto de Polymath (proyectos colaborativos en los que trabajan cientos de matemáticos a través de una página web), creado por el propio de Grey.

Con este avance, ya sabemos que para poder colorear cualquier grafo harán falta cinco, seis o siete colores diferentes. Para zanjar el problema existen dos posibilidades: que usando ideas parecidas a las de De Grey se encuentren estructuras con gran cantidad de puntos que requieran muchos colores para ser coloreadas (él ha encontrado una que necesita cinco, se trataría de encontrar otra con seis y, para solucionar el problema, necesitaríamos otra con siete). Así sabríamos que el número necesario para colorear el plano de forma que cualquier par de puntos a distancia uno tengan diferente color es siete. Si, por el contrario, la solución no es siete, es posible que sean necesarias nuevas técnicas totalmente desconocidas hasta el momento, porque no bastaría con ir descartando opciones con contraejemplos, sino dar un razonamiento general.

Alberto Márquez es Catedrático de Matemática Aplicada de la Universidad de Sevilla y Ágata Timón es responsable de Comunicación y Divulgación en el ICMAT

Café y Teoremas es una sección dedicada a las matemáticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matemáticas (ICMAT), en la que los investigadores y miembros del centro describen los últimos avances de esta disciplina, comparten puntos de encuentro entre las matemáticas y otras expresiones sociales y culturales, y recuerdan a quienes marcaron su desarrollo y supieron transformar café en teoremas. El nombre evoca la definición del matemático húngaro Alfred Rényi: “Un matemático es una máquina que transforma café en teoremas”.