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

A lower bound on the iteration number of k-WL

Lax119563.IterationNumber · concepts/Lax119563/IterationNumber.lean · lax-119563

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Theorem. Let k≥3k \geq 3 be fixed. For every n0∈Nn_0 \in \mathbb N there are some n≥n0n \geq n_0 and nn-vertex colored graphs G0,G1G_0, G_1 such that kk-WL distinguishes G0G_0 and G1G_1, but only after Ωk(nk−1)\Omega_k(n^{k-1}) iterations.

    This matches the upper bound of Ok(nk−1)O_k(n^{k-1}) on the number of iterations after which kk-WL stabilizes.

    Concept map
    3 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax119563.WeisfeilerLeman
    2
    3/-!
    4---
    5title: A lower bound on the iteration number of k-WL
    6type: theorem
    7---
    8**Theorem.** Let k≥3k \geq 3 be fixed. For every n0∈Nn_0 \in \mathbb N there are some
    9n≥n0n \geq n_0 and nn-vertex colored graphs G0,G1G_0, G_1 such that kk-WL distinguishes G0G_0
    10and G1G_1, but only after Ωk(nk−1)\Omega_k(n^{k-1}) iterations.
    11
    12This matches the upper bound of Ok(nk−1)O_k(n^{k-1}) on the number of iterations after which
    13kk-WL stabilizes.
    14
    15# Implementation notes
    16
    17The constant hidden in Ωk\Omega_k is made explicit: there is a CC, depending on kk only,
    18such that kk-WL does not distinguish G0G_0 and G1G_1 after any rr rounds with
    19Cr<nk−1C r < n^{k-1}.
    20-/
    21
    22open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman
    23
    24namespace 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. -/
    29axiom 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
    34end Lax119563.IterationNumber
    35
    Show Proof

    Implementation notes

    The constant hidden in Ωk\Omega_k is made explicit: there is a CC, depending on kk only, such that kk-WL does not distinguish G0G_0 and G1G_1 after any rr rounds with Cr<nk−1C r < n^{k-1}.

    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…