7 278 601 292 779 396 715. Exactamente esa cantidad de grafos cordales diferentes (grafos sin ciclos inducidos de longitud cuatro o más) se pueden construir sobre veinte vértices, si se cuentan las estructuras sin nombres. Este número no es un rompecabezas para un superordenador, sino el resultado exacto de un nuevo algoritmo que mira la simetría como una herramienta, no como un estorbo.

Imagine un caleidoscopio: unos cuantos vidrios de colores generan un patrón infinito al multiplicarse en los espejos. En el problema de enumerar grafos no etiquetados (donde los vértices son indistinguibles), las simetrías son esos mismos espejos: permutaciones de los vértices que dejan el grafo inalterado. Para contar todos los grafos no etiquetados, es necesario considerar cada posible reflexión. Y aquí entra el lema de Burnside: el promedio, sobre todas las permutaciones, del número de grafos que permanecen fijos bajo cada permutación es igual al número buscado. El problema es que hay un factorial de permutaciones en el número de vértices, y para n=20 son 2,43×$10^{18}$ opciones. Pero el algoritmo sortea esta avalancha apoyándose en la «evaporación».

La evaporación es un proceso elegante: de un grafo cordal se eliminan una y otra vez los vértices simpliciales (aquellos cuyos vecinos forman una clique) hasta que solo queda el grafo vacío. En 2021, un enfoque con espíritu von Neumann — la programación dinámica — permitió contar rápidamente los grafos cordales etiquetados. Pero ¿cómo trasladarlo al mundo de las simetrías? Respuesta: haciendo que se evaporen órbitas enteras — grupos de vértices que se transforman unos en otros bajo la permutación. Así surge la evaporación orbital.

El momento más delicado es cuando la órbita no es homogénea y sus partes están unidas por puentes complicados. Entonces entra en juego la descomposición de haces divisores. Si la permutación contiene un ciclo de longitud c, y una componente conexa del grafo se extiende sobre varias órbitas, esta se descompone en d «haces» idénticos, cada uno simétrico respecto a un grupo más pequeño, como si en el caleidoscopio se reflejara no todo el vidrio, sino una parte de él. Este truco reduce el cálculo a una llamada recursiva del mismo problema en un mundo reducido: en lugar del grupo original, se considera un grupo de orden d veces menor. La recursión es la base del esquema computacional que recorre meticulosamente los tipos de ciclos y acumula las contribuciones.

Así, paso a paso, se logró llegar hasta n=20. El algoritmo no solo coincidió con los valores conocidos hasta n=15, sino que también superó la verificación mediante la transformación euleriana, que relaciona grafos generales y conexos, y la confirmación directa para tipos de ciclos pequeños. Su complejidad es n elevado a la raíz de n, muy por debajo de la exponencial, lo que deja margen para futuros récords.

El caleidoscopio de simetrías no solo actualizó la enciclopedia OEIS. Mostró cómo los algoritmos de «evaporación» se llevan bien con la teoría de grupos y propuso un esquema universal para otras clases de grafos: de intervalos, cordales bipartitos, de comparabilidad. En perspectiva, la computación distribuida y un salto hacia n=22. Y la metáfora de los haces divisores quizás sea útil en pruebas de modelos generativos de redes o en problemas de quimioinformática, donde hay que enumerar estructuras moleculares no isomorfas.

Volvamos al número 7 278 601 292 779 396 715. Detrás de él no hay caos, sino una arquitectura rigurosa de reflexiones. Cada combinación de aristas recuerda su órbita en el laberinto de espejos de las simetrías, y ahora este laberinto se puede recorrer sin pérdidas.