Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax3.NowhereDenseSplitter

Splitter wins on nowhere dense classes

concepts/Lax3/NowhereDenseSplitter.lean · lax-3

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.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Evidence

    Each proof establishes this claim relative to its assumptions.

    Theorem

    On a nowhere dense class, Splitter wins the isolation splitter game: for every radius r there are a round bound and a batch bound m, depending only on the class and r, such that Splitter wins the (, m, r)-game on every member.

    This is Lemma 4.2 of Chapter 4 of the source lecture notes (2019/20 edition) — Theorem 4.2 of Grohe–Kreutzer–Siebertz in the batch form — transposed to the isolation variant of the game. The bound is the qualitative heart of the model-checking algorithm: the game tree has bounded depth, so the recursion that descends it does bounded work per vertex.

    Lean source view on GitHub

    1import Lax3.SplitterGame
    2import Lax12.NowhereDenseClasses
    3
    4/-!
    5---
    6title: Splitter wins on nowhere dense classes
    7type: theorem
    8---
    9On a nowhere dense class, Splitter wins the isolation splitter game:
    10for every radius *r* there are a round bound *ℓ* and a batch bound *m*,
    11depending only on the class and *r*, such that Splitter wins the
    12(*ℓ*, *m*, *r*)-game on every member.
    13
    14This is Lemma 4.2 of Chapter 4 of the source lecture notes (2019/20
    15edition) — Theorem 4.2 of Grohe–Kreutzer–Siebertz in the batch form —
    16transposed to the isolation variant of the game. The bound is the
    17qualitative heart of the model-checking algorithm: the game tree has
    18bounded depth, so the recursion that descends it does bounded work per
    19vertex.
    20
    21# Formalization notes
    22
    23The hypothesis is `Lax12.NowhereDense` verbatim, and the proof to come
    24derives the strategy from Lax12's `uniformlyQuasiWide_of_nowhereDense`,
    25following the notes' path-maintenance strategy: Splitter maintains
    26BFS paths to the connector vertices of earlier rounds and isolates the
    27still-active vertices of those paths, with `ℓ = N_r(2·s_r + 2)` and
    28`m = ℓ · (r + 1)` for the quasi-wideness margins `N_r, s_r`. Two
    29remarks recorded for the discharge. First, the notes state
    30`ℓ = N_r(2·s_r + 1)`, but their proof extracts `s_r + 1` pairwise
    31disjoint paths so that one avoids the deleted separator, which needs
    32the `+ 2` form; the formalization takes the `+ 2` form and fixes the
    33slip silently. Second, the isolation variant needs no new argument
    34over the notes' deletion variant: arenas only lose edges, so a vertex
    35isolated in some round has no incident edge in any later arena — the
    36paths the strategy cuts stay cut, and the distance-independent set the
    37contradiction extracts is independent in exactly Lax12's
    38`deleteVerts` sense, which is the conclusion shape of the endorsed
    39quasi-wideness theorem.
    40
    41The statement quantifies the strategy away: it asserts winning
    42positions, not a strategy function. The explicit strategy — the object
    43the model-checking program executes — is constructed proofs-side with
    44this axiom's discharge and consumed there by the program-correctness
    45proofs; surfacing it would freeze implementation detail into the
    46concept.
    47-/
    48
    49namespace Lax3.NowhereDenseSplitter
    50
    51open Lax3.SplitterGame
    52open Lax12.GraphClasses Lax12.NowhereDenseClasses
    53
    54/-- On a nowhere dense class, for every radius there are round and
    55batch bounds with which Splitter wins the isolation splitter game on
    56every member. -/
    57axiom splitterWins_of_nowhereDense (C : GraphClass) (h : NowhereDense C)
    58 (r : ℕ) :
    59 ∃ ℓ m : ℕ, ∀ (n : ℕ) (G : SimpleGraph (Fin n)), C n G →
    60 SplitterWins m r ℓ G
    61
    62end Lax3.NowhereDenseSplitter
    63
    Show Proof

    Formalization notes

    The hypothesis is Lax12.NowhereDenseLax12.NowhereDense verbatim, and the proof to come derives the strategy from Lax12's uniformlyQuasiWideofnowhereDenseuniformlyQuasiWide_of_nowhereDense, following the notes' path-maintenance strategy: Splitter maintains BFS paths to the connector vertices of earlier rounds and isolates the still-active vertices of those paths, with =Nr(2sr+2)ℓ = N_r(2·s_r + 2) and m=(r+1)m = ℓ · (r + 1) for the quasi-wideness margins Nr,srN_r, s_r. Two remarks recorded for the discharge. First, the notes state =Nr(2sr+1)ℓ = N_r(2·s_r + 1), but their proof extracts sr+1s_r + 1 pairwise disjoint paths so that one avoids the deleted separator, which needs the +2+ 2 form; the formalization takes the +2+ 2 form and fixes the slip silently. Second, the isolation variant needs no new argument over the notes' deletion variant: arenas only lose edges, so a vertex isolated in some round has no incident edge in any later arena — the paths the strategy cuts stay cut, and the distance-independent set the contradiction extracts is independent in exactly Lax12's deleteVertsdeleteVerts sense, which is the conclusion shape of the endorsed quasi-wideness theorem.

    The statement quantifies the strategy away: it asserts winning positions, not a strategy function. The explicit strategy — the object the model-checking program executes — is constructed proofs-side with this axiom's discharge and consumed there by the program-correctness proofs; surfacing it would freeze implementation detail into the concept.

    Used by

    none

    From Mathlib

    none

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…