El enigma del problema de Hadwiger-Nelson

El problema de Hadwiger-Nelson es uno de los más conocidos en el campo de la geometría discreta. La pregunta es: ¿cuántos colores se necesitan para pintar el plano de modo que dos puntos a una distancia de una unidad se pinten de colores diferentes? Aunque parece una pregunta sencilla, lleva más de 70 años sin respuesta. Sin embargo, gracias a las herramientas de aprendizaje automático, se ha logrado avanzar en su comprensión.

Explorando las posibilidades

Se sabe que el número de colores necesarios podría ser cinco, seis o siete. Para determinar el número mínimo, se buscan configuraciones de puntos que no puedan pintarse con un número menor de colores y cumplan la propiedad indicada. Así, se deduce que al menos se necesitan n+1 colores.

Es fácil ver que, como mínimo, se requieren tres colores. Tomando un triángulo equilátero con lados de una unidad, se necesitan tres colores para evitar que dos vértices adyacentes tengan el mismo color.

Contribuciones históricas

En los años 60, los hermanos Leo y William Moser encontraron una configuración de siete puntos que requiere al menos cuatro colores. En 2018, Aubrey de Grey descubrió una configuración con más de 1000 puntos que necesita al menos cinco colores.

Limitaciones y posibilidades

Sabemos que no se necesitan más de siete colores porque existe una estrategia de coloración con ese número. Usando una teselación en forma de panal de abejas, podemos pintar el plano con siete colores, garantizando que dos puntos a distancia uno caen en hexágonos adyacentes de diferente color.

Sin embargo, el misterio persiste: podría existir una coloración desconocida que requiera menos colores.

Enfoques alternativos

Para avanzar en la investigación, los matemáticos imponen restricciones más débiles y resuelven el problema resultante. Esto ayuda a encontrar enfoques para la pregunta original, como el problema de Hadwiger-Nelson débil, analizando configuraciones válidas con distancias asociadas a cada color.

Por ejemplo, con n=4 colores y distancias diferentes, se busca una configuración en la que parejas de puntos del mismo color estén a una distancia mayor que la asociada al color.

Avances recientes

Investigadores del Zuse Institute Berlin y la Technische Universität Berlin han logrado una configuración válida con seis colores, donde el sexto color tiene una distancia relajada entre 0,354 y 0,657. Este resultado mejora investigaciones previas.

El uso del aprendizaje automático ha sido crucial. Una red neuronal ha generado representaciones que cumplen las condiciones deseadas, funcionando como un “oráculo aproximado”. Los investigadores interpretan esta información para avanzar hacia una solución.

Visualización y futuro

Los resultados permiten construir una teselación periódica de seis colores, donde el sexto color cumple condiciones más laxas.

Estas técnicas computacionales son prometedoras y podrían aplicarse en el futuro a problemas inabordables hoy, como la extensión del problema de Hadwiger-Nelson en el espacio.

Contribuciones académicas

Juanjo Rué es profesor del Departamento de Matemáticas de la Universitat Politècnica de Catalunya (UPC) y miembro del Instituto de Matemáticas de la UPC (IMTech).

Ágata A. Timón G Longoria es coordinadora de la Unidad de Cultura Matemática del ICMAT.

Café y Teoremas es una sección dedicada a las matemáticas, coordinada por el Instituto de Ciencias Matemáticas (ICMAT).

Edición y coordinación: Ágata Timón García-Longoria.