Splitter wins on nowhere dense classes
Lax3.NowhereDenseSplitter · concepts/Lax3/NowhereDenseSplitter.lean · lax-3
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
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.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax3.SplitterGame |
| 2 | import Lax199508.NowhereDenseClasses |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Splitter wins on nowhere dense classes |
| 7 | type: theorem |
| 8 | --- |
| 9 | On a nowhere dense class, Splitter wins the isolation splitter game: |
| 10 | for every radius *r* there are a round bound *ℓ* and a batch bound *m*, |
| 11 | depending only on the class and *r*, such that Splitter wins the |
| 12 | (*ℓ*, *m*, *r*)-game on every member. |
| 13 | |
| 14 | This is Lemma 4.2 of Chapter 4 of the source lecture notes (2019/20 |
| 15 | edition) — Theorem 4.2 of Grohe–Kreutzer–Siebertz in the batch form — |
| 16 | transposed to the isolation variant of the game. The bound is the |
| 17 | qualitative heart of the model-checking algorithm: the game tree has |
| 18 | bounded depth, so the recursion that descends it does bounded work per |
| 19 | vertex. |
| 20 | |
| 21 | # Formalization notes |
| 22 | |
| 23 | The hypothesis is `Lax199508.NowhereDense` verbatim, and the proof to come |
| 24 | derives the strategy from Lax199508's `uniformlyQuasiWide_of_nowhereDense`, |
| 25 | following the notes' path-maintenance strategy: Splitter maintains |
| 26 | BFS paths to the connector vertices of earlier rounds and isolates the |
| 27 | still-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 |
| 29 | remarks recorded for the discharge. First, the notes state |
| 30 | `ℓ = N_r(2·s_r + 1)`, but their proof extracts `s_r + 1` pairwise |
| 31 | disjoint paths so that one avoids the deleted separator, which needs |
| 32 | the `+ 2` form; the formalization takes the `+ 2` form and fixes the |
| 33 | slip silently. Second, the isolation variant needs no new argument |
| 34 | over the notes' deletion variant: arenas only lose edges, so a vertex |
| 35 | isolated in some round has no incident edge in any later arena — the |
| 36 | paths the strategy cuts stay cut, and the distance-independent set the |
| 37 | contradiction extracts is independent in exactly Lax199508's |
| 38 | `deleteVerts` sense, which is the conclusion shape of the endorsed |
| 39 | quasi-wideness theorem. |
| 40 | |
| 41 | The statement quantifies the strategy away: it asserts winning |
| 42 | positions, not a strategy function. The explicit strategy — the object |
| 43 | the model-checking program executes — is constructed proofs-side with |
| 44 | this axiom's discharge and consumed there by the program-correctness |
| 45 | proofs; surfacing it would freeze implementation detail into the |
| 46 | concept. |
| 47 | -/ |
| 48 | |
| 49 | namespace Lax3.NowhereDenseSplitter |
| 50 | |
| 51 | open Lax3.SplitterGame |
| 52 | open Lax199508.GraphClasses Lax199508.NowhereDenseClasses |
| 53 | |
| 54 | /-- On a nowhere dense class, for every radius there are round and |
| 55 | batch bounds with which Splitter wins the isolation splitter game on |
| 56 | every member. -/ |
| 57 | axiom 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 | |
| 62 | end Lax3.NowhereDenseSplitter |
| 63 |
Formalization notes
The hypothesis is verbatim, and the proof to come derives the strategy from Lax199508's , 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 and for the quasi-wideness margins . Two remarks recorded for the discharge. First, the notes state , but their proof extracts pairwise disjoint paths so that one avoids the deleted separator, which needs the form; the formalization takes the 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 Lax199508's 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.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments