GraphKind: autonomous structural discovery and emergent laws in observation universes

Argaña Silguero, Josué

doi:10.5281/zenodo.22747350

The problem

The color refinement (1-WL) summarizes a graph into a partition of its vertices. Which operations leave that partition intact?

T4: the color refinement of a graph and of its complement induce the same partition (same colors = same classes). Discovered by the engine, verified on all graphs of n≤7 and with a written proof.

The next question: if the observer compresses neighborhood counts with a function f and the operation is an involution ι, in which universes (f, ι) does T4 still hold?

The result

T4(ι, f) VIVE ⟺ ι ∈ Sₙ·K y (ι cambia el par ⟹ f(1) ≠ f(2))

K = {id, comp_dir, transp, comp_transp} ≅ Z₂×Z₂

The Klein group: two halves, two conditions. The operation must be global (relabel × K); if it changes the connected pair, the compression must distinguish 1 from 2.

The particular case: the count law

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

In the complement, a vertex with 1 neighbor in a class gets |c|−1 (which may be 2): if f collapses 1 and 2, the duality dies. What f does with 3, 4, 5… is irrelevant.

result	verification
The law `f(1)≠f(2)`	34/34 · 102/102
Characterization, n=4 exhaustive	96 exact (24·4), zero outside
T4 under the k-FWL hierarchy (≡ (k+1)-WL)	51/51 en k=1,2,3
Observer cascade (n≤7, 781,875 pairs)	26 → 0 (k=1 → k=2)
Real data	molecules 100/100 · CST 94/94

The cascade: apparent randomness (unseparated pairs) drops to zero as the observer rises. In n≤7, k*=2; the canonical pairs need k=2 and k=3.

The type change

Changing the type of the invariant, T4 changes mathematical category — and each row is a different kind of theorem:

Standard

invariant: partition · equality

T4 holds (proved)

Deterministic Z₃

invariant: orbit · periods

T4 dies (max 52.4%)

Random (process)

invariant: distribution · async WL

T4 dies (18.6%)

Random (object)

G(n,p) vs G(n,1−p)

T4 holds (almost surely)

k-FWL hierarchy

stronger observers

T4_k 51/51

Random involutions

invariant: ensemble measure

threshold = measure

How it was found

The engine proposed and verified T4 (blind conjecture bank, 68/68), massive verification sustained it and a written proof closed the standard case. Then the lab parameterized the universe and let the data choose the law: two human hypotheses were refuted before reaching the characterization.

An autonomous construction search found the best valid witness (cycle, 99.63%) — better than the human construction. And the errors were recorded:

1. Multiset of sizes weak invariant (C6 and 2·C3 share it) → colors.

2. Comparing colors across graphs they never match → compare partitions.

3. Indices in the initial coloring trivialized everything → degrees + adjacencies.

4. Separated multisets weak k-WL → correlated pairs (= k-FWL).

5. The wrongly built Shrikhande it was the Rook twice → caught by is_isomorphic.

Five own bugs caught by controls, none announced before verifying. The method is part of the result.

Reproducibility

The whole paper reproduces with one command. Every verification carries an assert with the exact number: if anything does not match, it fails.

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)

status (⇐) proved · (⇒) verified (n≤4 exhaustive, n=5 targeted, real data) · ∀n argument and external review: open, declared.