No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Definition
The (ℓ, m, r)-splitter game is played on a graph by two players, Connector and Splitter. In each round, Connector picks a vertex v of the current arena; the arena is restricted to the ball of radius r around v; then Splitter picks a batch W of at most m vertices inside that ball and isolates it — every edge incident to W is deleted. Splitter wins when the arena becomes edgeless; if that has not happened after ℓ rounds, Connector wins.
The game is Definition 4.1 of Chapter 4 of the source lecture notes (2019/20 edition), in an isolation variant: where the notes delete Splitter's vertices from the arena, here the batch keeps its vertices and loses its incident edges, and the winning condition "the arena is empty" becomes "the arena is edgeless". Vertices never disappear, so every arena of a play lives on the vertex set of the original graph. The model-checking algorithm of this submission descends the game tree of this variant: keeping the vertices is what lets its rewriting step translate formulas through an isolation uniformly, with no case split on whether a variable lands on the batch.
Lean source view on GitHub
| 1 | import Lax3.ColoredGraphs |
| 2 | import Lax12.UniformQuasiWideness |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: The isolation splitter game |
| 7 | type: definition |
| 8 | --- |
| 9 | The (*ℓ*, *m*, *r*)-splitter game is played on a graph by two players, |
| 10 | Connector and Splitter. In each round, Connector picks a vertex *v* of |
| 11 | the current arena; the arena is restricted to the ball of radius *r* |
| 12 | around *v*; then Splitter picks a batch *W* of at most *m* vertices |
| 13 | inside that ball and isolates it — every edge incident to *W* is |
| 14 | deleted. Splitter wins when the arena becomes edgeless; if that has not |
| 15 | happened after *ℓ* rounds, Connector wins. |
| 16 | |
| 17 | The game is Definition 4.1 of Chapter 4 of the source lecture notes |
| 18 | (2019/20 edition), in an *isolation* variant: where the notes delete |
| 19 | Splitter's vertices from the arena, here the batch keeps its vertices |
| 20 | and loses its incident edges, and the winning condition "the arena is |
| 21 | empty" becomes "the arena is edgeless". Vertices never disappear, so |
| 22 | every arena of a play lives on the vertex set of the original graph. |
| 23 | The model-checking algorithm of this submission descends the game tree |
| 24 | of this variant: keeping the vertices is what lets its rewriting step |
| 25 | translate formulas through an isolation uniformly, with no case split |
| 26 | on whether a variable lands on the batch. |
| 27 | |
| 28 | # Formalization notes |
| 29 | |
| 30 | Both moves of a round are the same operation: restricting to the ball |
| 31 | around Connector's vertex is `deleteVerts` of the ball's complement, |
| 32 | and isolating Splitter's batch is `deleteVerts` of the batch — |
| 33 | Lax12's `deleteVerts`, which removes the edges incident to a set and |
| 34 | keeps the vertex type, is used for both, and is not restated here. |
| 35 | Arenas therefore only ever lose edges, which is the invariant the win |
| 36 | proof and the evaluator downstream both ride on (a vertex isolated |
| 37 | once is isolated in every later arena). |
| 38 | |
| 39 | `SplitterWins m r ℓ G` is defined by recursion on the remaining round |
| 40 | budget: with budget `0` Splitter has won exactly if the arena is |
| 41 | edgeless; with positive budget, if the arena is edgeless or for every |
| 42 | Connector move there is a batch after which he wins with the rest of |
| 43 | the budget. This says exactly "Splitter has a winning strategy within |
| 44 | `ℓ` rounds" without carrying strategy functions on the surface; the |
| 45 | explicit strategy — the object the algorithm executes — appears |
| 46 | proofs-side with the win theorem's discharge. (An inductive |
| 47 | winning-position predicate would say the same thing, but its step |
| 48 | constructor nests the ∀/∃ alternation of a round through `Exists`, |
| 49 | which Lean's kernel rejects as a nested inductive; the recursion on |
| 50 | the budget is the same mathematics and unfolds one round at a time.) |
| 51 | Allowing the edgeless win at any budget, rather than only after a |
| 52 | move, only enlarges Splitter's winning positions by games he has |
| 53 | already won and matches the algorithm's base case, which stops at an |
| 54 | edgeless arena before playing a round. |
| 55 | |
| 56 | The batch is a `Set` with an `ncard` bound, the idiom of Lax12's |
| 57 | quasi-wideness statements. The edgeless condition is `G = ⊥`, |
| 58 | mathlib's empty graph. |
| 59 | -/ |
| 60 | |
| 61 | namespace Lax3.SplitterGame |
| 62 | |
| 63 | open Lax3.ColoredGraphs |
| 64 | open Lax12.UniformQuasiWideness |
| 65 | |
| 66 | /-- Winning positions of Splitter in the (`ℓ`, `m`, `r`)-isolation |
| 67 | splitter game, by recursion on the remaining budget `ℓ`: the arena `G` |
| 68 | is already edgeless, or a round is left and for every vertex Connector |
| 69 | plays there is a batch of at most `m` vertices of its `r`-ball whose |
| 70 | isolation, after restricting the arena to that ball, is a winning |
| 71 | position with one round fewer. -/ |
| 72 | def SplitterWins {n : ℕ} (m r : ℕ) : ℕ → SimpleGraph (Fin n) → Prop |
| 73 | | 0, G => G = ⊥ |
| 74 | | ℓ + 1, G => G = ⊥ ∨ |
| 75 | ∀ v : Fin n, ∃ W : Set (Fin n), W ⊆ ball G r v ∧ W.ncard ≤ m ∧ |
| 76 | SplitterWins m r ℓ (deleteVerts (deleteVerts G (ball G r v)ᶜ) W) |
| 77 | |
| 78 | end Lax3.SplitterGame |
| 79 |
Formalization notes
Both moves of a round are the same operation: restricting to the ball around Connector's vertex is of the ball's complement, and isolating Splitter's batch is of the batch — Lax12's , which removes the edges incident to a set and keeps the vertex type, is used for both, and is not restated here. Arenas therefore only ever lose edges, which is the invariant the win proof and the evaluator downstream both ride on (a vertex isolated once is isolated in every later arena).
is defined by recursion on the remaining round budget: with budget Splitter has won exactly if the arena is edgeless; with positive budget, if the arena is edgeless or for every Connector move there is a batch after which he wins with the rest of the budget. This says exactly "Splitter has a winning strategy within rounds" without carrying strategy functions on the surface; the explicit strategy — the object the algorithm executes — appears proofs-side with the win theorem's discharge. (An inductive winning-position predicate would say the same thing, but its step constructor nests the ∀/∃ alternation of a round through , which Lean's kernel rejects as a nested inductive; the recursion on the budget is the same mathematics and unfolds one round at a time.) Allowing the edgeless win at any budget, rather than only after a move, only enlarges Splitter's winning positions by games he has already won and matches the algorithm's base case, which stops at an edgeless arena before playing a round.
The batch is a with an bound, the idiom of Lax12's quasi-wideness statements. The edgeless condition is , mathlib's empty graph.
Used by
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