Stabilization of k-WL
Lax119563.Stabilization · concepts/Lax119563/Stabilization.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Theorem (Döring and Neuen). Let be fixed. On every colored graph with vertices, -WL stabilizes after rounds.
More precisely, Döring and Neuen prove the bound for and the bound for .
Concept map
Lean source view on GitHub
| 1 | import Lax119563.WeisfeilerLeman |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Stabilization of k-WL |
| 6 | type: theorem |
| 7 | --- |
| 8 | **Theorem** (Döring and Neuen). Let be fixed. On every colored graph with |
| 9 | vertices, -WL stabilizes after rounds. |
| 10 | |
| 11 | More precisely, Döring and Neuen prove the bound for and the bound |
| 12 | for . |
| 13 | |
| 14 | # Implementation notes |
| 15 | |
| 16 | The constant hidden in is made explicit: there is a , depending on only, such |
| 17 | that -WL stabilizes after some number of rounds on every colored graph |
| 18 | with vertices. |
| 19 | -/ |
| 20 | |
| 21 | open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman |
| 22 | |
| 23 | namespace Lax119563.Stabilization |
| 24 | |
| 25 | /-- **Stabilization bound.** For `k ≥ 2`, `k`-WL stabilizes after `O_k(n ^ (k - 1))` rounds |
| 26 | on every colored graph with `n` vertices. -/ |
| 27 | axiom stabilization_bound (k : ℕ) (hk : 2 ≤ k) : |
| 28 | ∃ C : ℕ, ∀ G : ColoredGraph, ∃ r ≤ C * G.n ^ (k - 1), StabilizesAfter k r G |
| 29 | |
| 30 | end Lax119563.Stabilization |
| 31 |
Implementation notes
The constant hidden in is made explicit: there is a , depending on only, such that -WL stabilizes after some number of rounds on every colored graph with vertices.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments