Un aficionado hace el primer avance 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. 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.

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, ¿existe una cota 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. 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).

En 1961 los hermanos William y Leo Moser dieron una configuración de siete puntos denominada "huso de Moser", 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.