Lax3.NowhereDenseSplitter
Splitter wins on nowhere dense classes
concepts/Lax3/NowhereDenseSplitter.lean · lax-3
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
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
| 1 | import Lax3.SplitterGame |
| 2 | import Lax12.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 `Lax12.NowhereDense` verbatim, and the proof to come |
| 24 | derives the strategy from Lax12'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 Lax12'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 Lax12.GraphClasses Lax12.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 Lax12'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 Lax12'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.
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