Proof of `A lower bound on the iteration number of k-WL`
groundedproofs/Lax119563Proofs/Counter/Main.lean · lax-119563
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Fix and compile the counter implicit parity system (main location carrying all counter values, three equality schemas per increment position, endpoints initialized and ) with the row-space compiler.
- Its conflict round is finite and at least (, via a potential argument along the chain of equalities).
- Its size parameter is at most (): the coordinates of the domain of an increment at position have fixed bits in the rows below , which bounds both the domain size and the rank of the restricted check matrix.
- Duplicator survives rounds of the bijective -pebble game, so the graphs have equal size and, by the game characterization, every distinguishing round satisfies ; Spoiler wins eventually, so -WL distinguishes the graphs.
- Hence .
- Since -WL distinguishes two graphs after at most rounds if at all (), , so choosing large forces .