A lower bound on the iteration number of k-WL
Lax119563.IterationNumber · concepts/Lax119563/IterationNumber.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Theorem. Let be fixed. For every there are some and -vertex colored graphs such that -WL distinguishes and , but only after iterations.
This matches the upper bound of on the number of iterations after which -WL stabilizes.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax119563.WeisfeilerLeman |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: A lower bound on the iteration number of k-WL |
| 6 | type: theorem |
| 7 | --- |
| 8 | **Theorem.** Let be fixed. For every there are some |
| 9 | and -vertex colored graphs such that -WL distinguishes |
| 10 | and , but only after iterations. |
| 11 | |
| 12 | This matches the upper bound of on the number of iterations after which |
| 13 | -WL stabilizes. |
| 14 | |
| 15 | # Implementation notes |
| 16 | |
| 17 | The constant hidden in is made explicit: there is a , depending on only, |
| 18 | such that -WL does not distinguish and after any rounds with |
| 19 | . |
| 20 | -/ |
| 21 | |
| 22 | open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman |
| 23 | |
| 24 | namespace Lax119563.IterationNumber |
| 25 | |
| 26 | /-- **Iteration number lower bound.** For `k ≥ 3` there are arbitrarily large pairs of |
| 27 | `n`-vertex colored graphs which `k`-WL distinguishes, but not within fewer than |
| 28 | `n ^ (k - 1) / C` rounds. -/ |
| 29 | axiom iteration_number_lower_bound (k : ℕ) (hk : 3 ≤ k) : |
| 30 | ∃ C : ℕ, ∀ n₀ : ℕ, ∃ n ≥ n₀, ∃ G₀ G₁ : ColoredGraph, |
| 31 | G₀.n = n ∧ G₁.n = n ∧ Distinguishes k G₀ G₁ ∧ |
| 32 | ∀ r : ℕ, DistinguishesAfter k r G₀ G₁ → n ^ (k - 1) ≤ C * r |
| 33 | |
| 34 | end Lax119563.IterationNumber |
| 35 |
Implementation notes
The constant hidden in is made explicit: there is a , depending on only, such that -WL does not distinguish and after any rounds with .
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments