UNA IA RESUELVE UN ROMPECABEZAS DE COLOREADO

Tomemos una red de puntos unidos por líneas, lo que los matemáticos llaman un grafo. Ahora coloreemos los puntos de modo que dos puntos unidos por una línea nunca tengan el mismo color. El menor número de colores que lo permite es el número cromático del grafo. Un caso particular famoso es el teorema de los cuatro colores, demostrado en 1977, cuyo título lo dice todo: «Every planar map is four colorable» (todo mapa plano puede colorearse con cuatro colores).

La apuesta de Hadwiger en 1943

En 1943, Hadwiger propuso una regla general para todos los grafos. Reduzcamos un grafo borrando puntos o líneas, y fusionando dos puntos unidos en uno solo. El resultado se llama un menor. Hadwiger se fijó en el mayor grafo completo —un grupo en el que cada punto está unido a todos los demás— que puede obtenerse así, y conjeturó que el número de colores necesarios nunca supera el tamaño de ese grupo.

El artículo la califica de «uno de los problemas más antiguos y fundamentales de la teoría de grafos». Solo está demostrada para casos pequeños: hasta grupos de cinco, donde resulta equivalente al teorema de los cuatro colores o reducible a él. A partir de seis, sigue abierta.

Acercarse, logaritmo a logaritmo

Como el enunciado exacto se resiste, los investigadores intentaron acotar el número de colores mediante alguna función del tamaño del grupo que creciera lo más despacio posible. El artículo repasa los avances. Durante décadas, la mejor cota crecía algo más rápido que de forma proporcional, por un factor en el que intervenía la raíz cuadrada de un logaritmo. Hace unos años, Norin, Postle y Song rompieron esa barrera. Delcourt y Postle la mejoraron después y, sobre todo, demostraron que basta con ocuparse de grafos bastante pequeños. Liu y Luo rebajaron el factor adicional a un triple logaritmo.

El punto de llegada natural es la conjetura lineal de Hadwiger: siempre basta con un múltiplo fijo del tamaño del grupo. Eso es lo que Sergey Norin, de la Universidad McGill de Montreal, y Raphael Steiner, de la ETH de Zúrich, afirman ahora demostrar.

El papel de la máquina

Los autores lo dicen claramente: la demostración la encontró GPT-6 Astra, un modelo de OpenAI, siguiendo sus indicaciones. Primero le pidieron que demostrara el caso de los grafos muy densos, que creían que era la pieza que faltaba. Lo consiguió, escriben, «tras solo un par de horas y algo de ánimo». Cuando le pidieron que hiciera explícita una dependencia, cubrió los grafos hasta cierto tamaño, pero no del todo el rango necesario. Entonces le pidieron una idea original para salvar la distancia, y de ahí salió el paso de «bootstrap» de la demostración final. Casi ninguna de las ideas concretas de demostración de los propios autores sobrevivió, dicen, salvo una sugerencia sobre las contracciones.

La redacción es humana. Otro modelo de OpenAI ayudó con la corrección y la bibliografía. Los autores informan de que Codex, de OpenAI, produjo una versión formal, verificable por máquina, de toda la demostración en el asistente de demostraciones Lean, publicada en línea junto con un primer borrador escrito por la IA. Asumen la plena responsabilidad de las matemáticas.

Dentro de la demostración

El razonamiento tiene dos mitades:

1. Grafos pequeños, pocos colores. Para grafos no mucho mayores que el límite del grupo, los autores muestran que basta con unas cuatro veces el tamaño del grupo. El punto de partida es un resultado de Reed y Seymour de 1998: una forma relajada, «fraccionaria», de coloreado ya obedece la regla lineal con factor dos. El nuevo trabajo convierte coloreados fraccionarios en coloreados reales añadiendo algunas líneas extra al grafo y encontrando enormes emparejamientos en una estructura auxiliar.
2. Un bootstrap. Un segundo argumento amplía en cada paso el rango de tamaños de grafo cubiertos en un factor de cuatro tercios en el exponente, a costa de una constante mayor. Diez pasos llevan el rango de un tercio a unos 5,92, por encima del umbral de 5 que exige la reducción de Delcourt y Postle. Esta mitad usa un viejo truco debido a Gyárfás que, según los autores, nunca se había aplicado a este problema.

Los autores describen la demostración como construida con herramientas conocidas: «contenida en la envolvente convexa de los resultados existentes», aunque no en un borde evidente de ella.

Lo que sigue abierto

La constante es enorme: una estimación aproximada da unos 10¹⁰⁰. Los autores ven margen para bajarla de 10¹⁰, pero creen que llegar, por ejemplo, a 100 requeriría ideas nuevas. La conjetura exacta de Hadwiger queda intacta: «No nos decidimos», escriben. El artículo es un preprint; 41 páginas de matemáticas nuevas se enfrentarán ahora al escrutinio de otros expertos.