1 La pregunta
Dos grafos son isomorfos si existe una biyección entre sus vértices que preserva las aristas. Decidirlo es el problema del isomorfismo de grafos: el ejemplo canónico de un problema en NP que no se sabe si es P ni si es NP-completo.
Su versión estructural pregunta si existe una huella completa: un invariante que distinga todo par de grafos no isomorfos y que se calcule en tiempo polinómico. Nadie lo encontró. Nadie probó que no exista.
Lo que se sabe. Hay algoritmos excelentes en la práctica
(nauty/Traces, con individualización y refinamiento) y un
algoritmo cuasi-polinomial (Babai, 2016). Pero todos los invariantes conocidos son
incompletos: el refinamiento de color no distingue C₆ de
2·C₃, y la jerarquía k-WL es estrictamente creciente
(Cai–Fürer–Immerman, 1992): para cada k hay pares que solo
k+1 separa.
Este sitio cuenta lo que medimos sobre esa frontera. Cada número viene de un freeze del laboratorio (un resultado congelado antes de interpretarlo) y cada demo se computa en tu navegador con el mismo algoritmo del motor.
2 El motor
El kernel del laboratorio es el refinamiento de color (1-WL): cada vértice empieza con su grado; en cada ronda, su color se vuelve el hash de su color anterior más el multiset de colores de sus vecinos. Cuando dos vértices terminan con el mismo color, el invariante no los distingue.
La pregunta del laboratorio fue otra: ¿qué pasa con ese invariante cuando cambia la observación — cuando el grafo se complementa, se apila en capas o cambia de aridad? La respuesta corta es T4: la partición de clases se preserva bajo complemento. Las etiquetas de color no: son hashes arbitrarios.
Demo 1 · T4 ronda a ronda
Un árbol binario (n=15) y su complemento. Movés la ronda y ves las clases. La partición coincide en cada nivel; los colores difieren porque las etiquetas son arbitrarias.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| G | 3 | 4 | 4 | 4 |
| Ḡ | 3 | 4 | 4 | 4 |
Fuente: resultados/t4-arbol-trayectoria.json — el script
que genera la figura calcula la trayectoria y la asserta contra el motor
(nada interpretado a mano).
3 T4 y su precio
T4 dice que el perfil del refinamiento es invariante bajo complemento. Eso tiene
un costo exacto: si imponemos complemento-invarianza, el cociente
G ~ Ḡ fusiona 6 168 pares en n≤8. Esa es la
información que T4 describe, cuantificada.
Y hay una tensión estructural: un invariante completo no puede ser
complemento-invariante. Si I(G) = I(Ḡ) para todo G,
entonces I identifica pares no isomorfos siempre que G no sea
autocomplementario — y la mayoría no lo es. La simetría que hace elegante al
invariante es la que lo vuelve incompleto.
assets/t4-particion.svg (v2).4 Los universos
El laboratorio parametrizó el universo de observación: la función que
comprime los conteos de vecinos y la involución que actúa. De ahí salió una
ley emergente: T4 vive ⟺ la involución es trivial, o es dual
global y el conteo distingue 1 de 2. La ley fue elegida por la tabla,
no por nosotros: dos hipótesis humanas fueron refutadas por los datos.
Un segundo ciclo la refinó hasta una caracterización
(T4(ι,f) ⟺ ι ∈ Sₙ·K y, cuando ι cambia el par,
f(1) ≠ f(2)): la pieza que faltaba era la uniformidad.
La dirección (⇐) está probada; la (⇒) verificada exhaustiva en n≤4 y dirigida en n=5.
assets/universos-mapa.svg (v2).5 Los observadores
Existen los observadores en la literatura; el orden entre ellos, medido lado a lado, no. En las anclas:
| observador | comportamiento medido |
|---|---|
| WL | = 2-WL en n≤9; falla en C₆/2·C₃ |
| 3-WL (estándar) | completa en n≤8; no separa Rook/Shrikhande |
| IR₁ | falla exactamente donde falla 3-WL |
| IR₂ | se comporta como 3-FWL ≡ 4-WL; sí separa Rook/Shrikhande |
| SNF del Laplaciano | separa Rook/Shrikhande |
| homomorfismos | separan donde WL acotado no alcanza |
6 La frontera medida
pares exhaustivos en n≤8: la familia
{WL, 2-WL, 3-WL} da cero colisiones. Sin 3-WL quedan 350.
grafos n=10 barridos exhaustivamente (11.1 h, 22 procesos): cero colisiones. La primera incompletitud no está en n=10.
primera falla conocida: el par Rook/Shrikhande (SRG(16,6,2,2), cospectrales).
La frontera exacta entre n=11 y n=15 queda abierta (el barrido es inabordable: 1019 millones de grafos en n=11). Eso no es una derrota: es el mapa.
Demo 2 · ¿Lo separa?
Elegí un par y un observador. Tu navegador corre el mismo refinamiento que el
motor (k-FWL correlacionada ≡ (k+1)-WL) y compara las
particiones. Los resultados esperados vienen del motor (freeze).
veredicto del navegador: —
7 Las leyes
Multicapa
Cuando el universo tiene L capas acopladas, T4 deja de ser una propiedad de un
grafo y pasa a ser una propiedad de la composición: vive si y solo si
el complemento actúa uniformemente sobre las capas. El grupo que preserva el perfil
se caracteriza como ℤ₂^L ⋊ S_L. La coherencia se midió en 1 298/1 298
casos (L=2) y 1 404/1 404 (L=3).
assets/multicapa-ley.svg (v2).Hipergrafos
En hipergrafos de aridad mezclada, la operación puede romper la invariancia; el dual por aridad la repara. Se midió en 261 000 casos (21 821 fusiones dirigidas, cero testigos de fallo): la frontera entre "rompe" y "repara" es el tipo de mensaje, no el tamaño. El dual entró al motor con partición correcta y un ahorro del 14.37% frente al 10.26% de la línea base.
assets/dual-aridad.svg (v2).8 Lo que NO resolvimos
- No encontramos el invariante completo universal. No existe, o no se sabe si existe.
- No probamos que sea imposible. Solo mostramos que ninguno de los observadores probados lo es en la clase medida.
- No resolvimos P vs NP. El isomorfismo sigue cuasi-polinomial (Babai, 2016).
- No medimos la frontera exacta entre n=11 y n=15. Es inabordable por barrido; la primera falla conocida es n=16.
- La dirección (⇒) de la caracterización multicapa está
verificada en n≤4 y dirigida en n=5; el
∀nsigue abierto.
9 El mapa
Convertimos una pregunta abierta en un objeto medible. No la resolvimos: la acotamos.
- La completitud vive en n≤10 (exhaustivo).
- La primera falla es n=16 (Rook/Shrikhande).
- La frontera exacta está entre esos dos.
- La incompletitud es relativa al par (universo, observador).
- El costo de la simetría es 6 168 pares.
- Hay una ley de composición multicapa y un reparo de hipergrafos.
«El universo habla una gramática; el isomorfismo pregunta si dos frases dicen lo mismo. Nosotros no respondimos la pregunta: dibujamos el mapa de dónde se puede responder.»