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

Lax3.SplitterGame

The isolation splitter game

concepts/Lax3/SplitterGame.lean · lax-3

definition

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

    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

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

    Formalization notes

    Both moves of a round are the same operation: restricting to the ball around Connector's vertex is deleteVertsdeleteVerts of the ball's complement, and isolating Splitter's batch is deleteVertsdeleteVerts of the batch — Lax12's deleteVertsdeleteVerts, 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).

    SplitterWinsmrGSplitterWins m r ℓ G is defined by recursion on the remaining round budget: with budget 00 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 ExistsExists, 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 SetSet with an ncardncard bound, the idiom of Lax12's quasi-wideness statements. The edgeless condition is G=G = ⊥, mathlib's empty graph.

    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…