Proof of `Stabilization of k-WL`
groundedproofs/Lax119563Proofs/Stabilization/Main.lean · lax-119563
What this proof establishes
no assumptions
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
We follow Döring and Neuen and take . Let , let have vertices, and suppose -WL does not stabilize after any of the rounds , i.e. . It suffices to show , which is .
The colorings are refining, compatible with equality and shufflable for every . For let and let be the space of complex matrices constant on the color classes of . Then is a weak chain: it contains the identity (compatibility with equality), is closed under conjugate transposition (shufflability), and (Lemma 6.2: an entry of a product is a count over the multiset part of the next color). Since forces (Lemma 4.7), the two-dimensional bound (Theorem 5.15, at most strict steps of a weak chain in ) bounds the number of rounds with by .
For the only is empty and , so . For let . Extendability (Lemma 6.4) and shufflability give Claim 6.5: if is not a color , then . Claim 6.6: if is witnessed by , and no splits in round , then (shufflability) and, by Claim 6.5 at round , ; so splits in round , or . Every split increases the number of classes of , which is at most . Taking all (instead of the sorted prefixes of the paper), .