GraphKind · preprint privado · 2026

Sobre los universos del
color refinement

Cuándo sobrevive un invariante estructural a un cambio de observación: la clasificación de las operaciones que preservan el perfil del color refinement bajo involución — y su prueba.

Leer el paper La prueba Reproducir EN
2 131 019 grafos (T4) 34/34 · 102/102 la ley 96 exactas en n=4 CI verde

El problema

El color refinement (1-WL) resume un grafo en una partición de sus vértices. ¿Qué operaciones dejan esa partición intacta?

G ⟶ complemento Ḡ I(G)=I(Ḡ)
T4: el color refinement de un grafo y el de su complemento inducen la misma partición (mismos colores = mismas clases). Descubierto por el motor, verificado en todos los grafos de n≤7 y con prueba escrita.

La pregunta que sigue: si el observador comprime los conteos de vecinos con una función f y la operación es una involución ι, ¿en qué universos (f, ι) sigue viviendo T4?

El resultado

T4(ι, f) VIVE  ⟺  ι ∈ Sₙ·K   y   (ι cambia el par ⟹ f(1) ≠ f(2))
K = {id, comp_dir, transp, comp_transp} ≅ Z₂×Z₂
id swap no · comp no transp swap sí · comp no comp_dir swap no · comp sí comp_transp swap sí · comp sí viven con toda f viven ⟺ f(1) ≠ f(2) La uniformidad une las dos mitades: fuera de K, todo muere (aunque preserve el par).
El grupo de Klein: dos mitades, dos condiciones. La operación debe ser global (relabel × K); si cambia el par conectado, la compresión debe distinguir 1 de 2.

El caso particular: la ley del conteo

T4 VIVE  ⟺  f(1) ≠ f(2)

En el complemento, un vértice con 1 vecino de una clase pasa a tener |c|−1 (que puede ser 2): si f colapsa 1 y 2, la dualidad muere. Lo que f haga con 3, 4, 5… es irrelevante.

resultadoverificación
La ley f(1)≠f(2) 34/34 · 102/102
Caracterización, n=4 exhaustivo 96 exactas (24·4), cero fuera
T4 bajo la jerarquía k-FWL (≡ (k+1)-WL) 51/51 en k=1,2,3
Cascada del observador (n≤7, 781 875 pares) 26 → 0 (k=1 → k=2)
Datos reales moléculas 100/100 · CST 94/94
26 0 k = 1 k = 2 k = 3 26 pares 1-WL-equivalentes 0: 2-WL los resuelve todos C6 vs 2·C3: k*=2 Rook vs Shrikhande: k*=3
La cascada: la aleatoriedad aparente (pares no separados) cae a cero al subir el observador. En n≤7, k*=2; los pares canónicos necesitan k=2 y k=3.

El cambio de tipo

Cambiando el tipo del invariante, T4 cambia de categoría matemática — y cada fila es un tipo distinto de teorema:

Estándar
invariante: partición · igualdad
T4 vive (probado)
Z₃ determinista
invariante: órbita · períodos
T4 muere (máx. 52.4%)
Aleatorio (proceso)
invariante: distribución · WL asíncrono
T4 muere (18.6%)
Aleatorio (objeto)
G(n,p) vs G(n,1−p)
T4 vive (casi seguro)
Jerarquía k-FWL
observadores más fuertes
T4_k 51/51
Involuciones aleatorias
invariante: medida del ensemble
umbral = medida

Cómo se encontró

El motor propuso y verificó T4 (banco de conjeturas ciego, 68/68), la verificación masiva lo sostuvo y una prueba escrita cerró el caso estándar. Después el laboratorio parametrizó el universo y dejó que los datos eligieran la ley: dos hipótesis humanas fueron refutadas antes de llegar a la caracterización.

Una búsqueda autónoma de construcciones encontró el mejor testigo válido (ciclo, 99.63%) — mejor que la construcción humana. Y los errores quedaron registrados:

1. Multiset de tamaños invariante débil (C6 y 2·C3 lo comparten) → colores.
2. Comparar colores entre grafos nunca coinciden → comparar particiones.
3. Índices en la coloración inicial trivializaba todo → grados + adyacencias.
4. MultiseTs separados k-WL débil → pares correlacionados (= k-FWL).
5. El Shrikhande mal construido era el Rook dos veces → cazado por is_isomorphic.

Cinco bugs propios cazados por controles, ninguno anunciado antes de verificar. El método es parte del resultado.

Reproducibilidad

Todo el paper se reproduce con un comando. Cada verificación lleva un assert con el número exacto: si algo no coincide, falla. 

git clone https://github.com/cripto-bot/graphkind-universos
cd graphkind-universos
python3 -m venv .venv && .venv/bin/pip install -r requirements.txt
bash reproduce.sh            # V1–V9 (~10-15 min)
bash reproduce.sh --rapido   # V1, V3, V5, V8 (~3 min)

estado (⇐) probada · (⇒) verificada (n≤4 exhaustivo, n=5 dirigido, datos reales) · argumento ∀n y revisión externa: abiertos, declarados.