While this submission is a draft, it cannot be used by other submissions.

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.

Read the Lean proof on GitHub

Description

We follow Döring and Neuen and take C=13C = 13. Let k=m+2k = m + 2, let GG have nn vertices, and suppose kk-WL does not stabilize after any of the rounds 0,…,r−10, …, r - 1, i.e. χ0≻χ1≻…≻χrχ_0 ≻ χ_1 ≻ … ≻ χ_r. It suffices to show r≤3n(k−2)+10n(k−1)r ≤ 3 n^(k-2) + 10 n^(k-1), which is <13n(k−1)+1< 13 n^(k-1) + 1.

The colorings χiχ_i are refining, compatible with equality and shufflable for every σ:[k]→[k]σ : [k] → [k]. For v∈V(k−2)v ∈ V^(k-2) let χiv(a,b)=χi(v,a,b)χ^v_i (a, b) = χ_i (v, a, b) and let ⟨χiv⟩⟨χ^v_i⟩ be the space of complex n×nn × n matrices constant on the color classes of χivχ^v_i. Then C1,⟨χ0v⟩,⟨χ1v⟩,…ℂ 1, ⟨χ^v_0⟩, ⟨χ^v_1⟩, … is a weak chain: it contains the identity (compatibility with equality), is closed under conjugate transposition (shufflability), and ⟨χiv⟩⟨χiv⟩⊆⟨χi+1v⟩⟨χ^v_i⟩ ⟨χ^v_i⟩ ⊆ ⟨χ^v_{i+1}⟩ (Lemma 6.2: an entry of a product is a count over the multiset part of the next color). Since ⟨χiv⟩=⟨χi+1v⟩⟨χ^v_i⟩ = ⟨χ^v_{i+1}⟩ forces χiv≡χi+1vχ^v_i ≡ χ^v_{i+1} (Lemma 4.7), the two-dimensional bound (Theorem 5.15, at most 10n10 n strict steps of a weak chain in Mn(C)M_n(ℂ)) bounds the number of rounds ii with χiv≻χi+1vχ^v_i ≻ χ^v_{i+1} by 10n10 n.

For k=2k = 2 the only vv is empty and χiv=χiχ^v_i = χ_i, so r≤10nr ≤ 10 n. For k≥3k ≥ 3 let χˉi(v)=χi(v,vk−2,vk−2)χ̄_i (v) = χ_i (v, v_{k-2}, v_{k-2}). Extendability (Lemma 6.4) and shufflability give Claim 6.5: if χi(v,w1,w2)χ_i (v, w_1, w_2) is not a color χi(v′,⋅,⋅)χ_i (v', ·, ·), then χˉi+2(v)≠χˉi+2(v′)χ̄_{i+2} (v) ≠ χ̄_{i+2} (v'). Claim 6.6: if χi≻χi+1χ_i ≻ χ_{i+1} is witnessed by (v,a,b)(v, a, b), (v′,c,d)(v', c, d) and no χwχ^w splits in round i+1i + 1, then χˉi(v)=χˉi(v′)χ̄_i (v) = χ̄_i (v') (shufflability) and, by Claim 6.5 at round i+1i + 1, χˉi+3(v)≠χˉi+3(v′)χ̄_{i+3} (v) ≠ χ̄_{i+3} (v'); so χˉχ̄ splits in round i+1i + 1, i+2i + 2 or i+3i + 3. Every χˉχ̄ split increases the number of classes of χˉχ̄, which is at most n(k−2)n^(k-2). Taking all v∈V(k−2)v ∈ V^(k-2) (instead of the sorted prefixes of the paper), r≤3n(k−2)+n(k−2)⋅10nr ≤ 3 n^(k-2) + n^(k-2) · 10 n.