UNIR CADA PUNTO CON TODOS LOS DEMÁS: EL MÍNIMO DE CRUCES, DEMOSTRADO

Pon cinco puntos en una hoja de papel y une cada par con una curva: diez curvas en total. Pueden doblarse como quieras, pero ninguna puede pasar por un tercer punto. Intenta evitar todos los cruces y fracasarás. Con cinco puntos, al menos 1 cruce es inevitable; con seis, al menos 3; con diez, al menos 60.

Los matemáticos llaman a un dibujo así un dibujo del grafo completo Kₙ —n puntos, cada par unido— y al menor número de cruces que puede alcanzar cualquier dibujo, su número de cruce. Martin Balko, de la Universidad Carolina de la República Checa, califica la cuestión de «uno de los problemas más famosos de la teoría topológica de grafos».

La cuenta de un artista

A finales de los años cincuenta, el artista británico Anthony Hill construyó dibujos de Kₙ con exactamente

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

cruces, donde ⌊ ⌋ significa redondear hacia abajo. La conjetura de que ningún dibujo puede hacerlo mejor la publicó por primera vez Guy, la discutieron después Harary y Hill, y la popularizaron Erdős y Guy. Se conoce como conjetura de Harary–Hill, o conjetura de Guy.

La fórmula crece deprisa:

• 4 puntos o menos: 0 cruces
• 5 puntos: 1
• 7 puntos: 9
• 10 puntos: 60
• 14 puntos: 315

Seis décadas de respuestas parciales

Existían dibujos con exactamente Z(n) cruces para cualquier número de puntos; lo difícil era demostrar que ningún dibujo lo hace mejor.

Durante más de sesenta años, eso solo se demostró para tipos especiales de dibujos: por ejemplo, con todos los puntos sobre una recta y cada curva mantenida a un lado de ella, o con los puntos sobre una esfera y cada curva siguiendo el camino más corto. El propio Balko, con Fulek y Kynčl, había resuelto una de esas clases. En 2021, los ordenadores habían confirmado la fórmula hasta 14 puntos. Para números muy grandes de puntos, los mejores resultados generales garantizaban al menos el 98,5 %, y después el 98,99 %, de Z(n).

Una demostración, y después otra más clara

En 2026, OpenAI anunció una demostración para cualquier número de puntos, que el artículo de Balko cita como un «OpenAI Math Release preprint» y a la que atribuye el teorema. El artículo no dice cómo se encontró esa demostración. En palabras de Balko, la original «es relativamente corta», pero «bastante difícil de seguir». Su preprint presenta una variante simplificada que, según escribe, «solo requiere conocimientos elementales de álgebra lineal y teoría de grafos». Otro matemático, Gelasio Salazar, prepara por separado una exposición detallada.

Contar coeficientes en lugar de cruces

Como los dibujos conocidos ya alcanzan Z(n), solo hay que demostrar la cota inferior. Hacen falta cuatro pasos.

1. Basta con los números impares. Un dibujo óptimo puede redibujarse de modo que las curvas que comparten un punto nunca se crucen; cada cruce involucra entonces 4 puntos distintos. Borra por turnos cada uno de los 6 puntos: cada dibujo restante de 5 puntos tiene al menos 1 cruce, y cada cruce sobrevive exactamente a 2 de los 6 borrados (desaparece cada vez que se borra uno de sus propios 4 puntos y sobrevive a los otros 2). Así que el doble de los cruces es al menos 6: al menos 3, que es Z(6). La misma cuenta funciona para cualquier número par.
2. Una familia de polinomios. Asigna a cada punto su propio número. Un cruce involucra dos curvas, es decir, cuatro puntos, es decir, cuatro números. Balko usa polinomios en cuatro variables, elegidos para que la familia tenga exactamente Z(n) coeficientes independientes cuando n es impar: para 7 puntos, 3 × 3 = 9.
3. Demasiado pocos cruces dejan margen. Pedir que un polinomio se anule en un cruce es una ecuación. Con menos ecuaciones que coeficientes libres, el álgebra lineal siempre deja una solución no nula. Así, un dibujo con menos de Z(n) cruces vendría acompañado de un polinomio no nulo que se anula en todos sus cruces; tomemos el de menor grado.
4. El plano se resiste. La geometría entra a través de un hecho clásico: un lazo cerrado en el plano cruza a otro de derecha a izquierda exactamente tantas veces como de izquierda a derecha. Con pesos bien elegidos, esto da una suma de cuadrados de los valores del polinomio, unos contados en positivo y otros en negativo, cuyo total es cero. Todos los términos positivos están en cruces, donde el polinomio vale cero, así que los negativos también deben anularse. Un segundo uso del hecho sobre los lazos lo hace divisible por un factor fijo; al dividir se obtiene un polinomio no nulo de menor grado con la misma propiedad, lo cual es imposible, ya que tomamos el de menor grado.

Ese argumento de signos es el principal cambio de Balko: sustituye el argumento original, «que involucra una forma bilineal no degenerada y complementos ortogonales». También demuestra de otra manera el hecho sobre los lazos y aísla cada punto de forma más directa.

Otras redes resueltas de golpe

La respuesta sigue siendo Z(n) si, en lugar de los cruces, se cuentan los pares de curvas que se cruzan alguna vez, o que se cruzan un número impar de veces, siempre que las curvas que comparten un punto no se encuentren en ningún otro sitio. Combinado con reducciones anteriores, el teorema también da los números de cruce exactos de grafos completos a los que se han quitado algunas aristas, de copias de un grafo completo encadenadas a lo largo de un camino o alrededor de un ciclo par, y de una familia de redes de aspecto fractal llamadas grafos de Sierpiński extendidos.

Si se quita una sola curva al grafo completo de 6 puntos, su mínimo baja de 3 cruces a 2; con 8 puntos, de 18 a 15.