The bijective pebble game
Lax119563.PebbleGame · concepts/Lax119563/PebbleGame.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Let be colored graphs and . The bijective -pebble game is played by two players, Spoiler and Duplicator, with pairs of pebbles. A game state is a partial map assigning to some pebble indices a pair . The game starts in the empty game state. If , Spoiler wins immediately. Otherwise, each round consists of the following steps:
- Spoiler chooses and lifts the -th pebble pair.
- Duplicator chooses a bijection .
- Spoiler chooses and places the -th pebble pair on and , i.e., sets .
Spoiler wins after a round if the map , for the placed pairs , is not a partial isomorphism: for all placed we need , , and .
For , Spoiler wins within rounds if he has a strategy that wins after one of the first rounds against every strategy of Duplicator; otherwise Duplicator survives rounds. Duplicator wins if she survives rounds for every .
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Logic.Equiv.Fin.Basic |
| 2 | import Lax119563.ColoredGraphs |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: The bijective pebble game |
| 7 | type: definition |
| 8 | --- |
| 9 | Let be colored graphs and . The *bijective -pebble game* |
| 10 | is played by two players, Spoiler and Duplicator, with pairs of |
| 11 | pebbles. A *game state* is a partial map assigning to some pebble indices a |
| 12 | pair . The game starts in the empty game state. If |
| 13 | , Spoiler wins immediately. Otherwise, each round consists of the |
| 14 | following steps: |
| 15 | |
| 16 | 1. Spoiler chooses and lifts the -th pebble pair. |
| 17 | 2. Duplicator chooses a bijection . |
| 18 | 3. Spoiler chooses and places the -th pebble pair on and , i.e., |
| 19 | sets . |
| 20 | |
| 21 | Spoiler wins after a round if the map , for the placed pairs |
| 22 | , is not a partial isomorphism: for all placed we need |
| 23 | , , and |
| 24 | . |
| 25 | |
| 26 | For , Spoiler *wins within rounds* if he has a strategy that wins after one of |
| 27 | the first rounds against every strategy of Duplicator; otherwise Duplicator *survives |
| 28 | rounds*. Duplicator *wins* if she survives rounds for every . |
| 29 | |
| 30 | # Implementation notes |
| 31 | |
| 32 | Survival is defined by recursion on the number of remaining rounds: Duplicator survives |
| 33 | rounds from a state if, for every pebble index Spoiler may lift, she has a |
| 34 | bijection such that every placement yields a partial isomorphism from which she survives |
| 35 | further rounds. |
| 36 | -/ |
| 37 | |
| 38 | open Lax119563.ColoredGraphs |
| 39 | |
| 40 | namespace Lax119563.PebbleGame |
| 41 | |
| 42 | /-- A game state of the `m`-pebble game: the pebble pairs currently placed. -/ |
| 43 | abbrev GameState (m : ℕ) (G H : ColoredGraph) := Fin m → Option (Fin G.n × Fin H.n) |
| 44 | |
| 45 | /-- The placed pebble pairs `p_i ↦ q_i` form a partial isomorphism. -/ |
| 46 | def IsPartialIso {m : ℕ} (G H : ColoredGraph) (S : GameState m G H) : Prop := |
| 47 | ∀ i j : Fin m, ∀ p q p' q', S i = some (p, q) → S j = some (p', q') → |
| 48 | (p = p' ↔ q = q') ∧ (G.graph.Adj p p' ↔ H.graph.Adj q q') ∧ G.color p = H.color q |
| 49 | |
| 50 | /-- Duplicator survives `r` further rounds of `BP_m(G, H)` from the game state `S`. -/ |
| 51 | def SurvivesFrom {m : ℕ} (G H : ColoredGraph) : ℕ → GameState m G H → Prop |
| 52 | | 0, _ => True |
| 53 | | r + 1, S => ∀ i : Fin m, ∃ f : Fin G.n ≃ Fin H.n, ∀ p : Fin G.n, |
| 54 | IsPartialIso G H (Function.update S i (some (p, f p))) ∧ |
| 55 | SurvivesFrom G H r (Function.update S i (some (p, f p))) |
| 56 | |
| 57 | /-- Duplicator survives `r` rounds of `BP_m(G, H)`, started in the empty game state. -/ |
| 58 | def DuplicatorSurvives (m r : ℕ) (G H : ColoredGraph) : Prop := |
| 59 | G.n = H.n ∧ SurvivesFrom (m := m) G H r (fun _ => none) |
| 60 | |
| 61 | /-- Spoiler wins `BP_m(G, H)` within `r` rounds. -/ |
| 62 | def SpoilerWinsWithin (m r : ℕ) (G H : ColoredGraph) : Prop := |
| 63 | ¬ DuplicatorSurvives m r G H |
| 64 | |
| 65 | /-- Duplicator wins `BP_m(G, H)`. -/ |
| 66 | def DuplicatorWins (m : ℕ) (G H : ColoredGraph) : Prop := |
| 67 | ∀ r, DuplicatorSurvives m r G H |
| 68 | |
| 69 | end Lax119563.PebbleGame |
| 70 |
Implementation notes
Survival is defined by recursion on the number of remaining rounds: Duplicator survives rounds from a state if, for every pebble index Spoiler may lift, she has a bijection such that every placement yields a partial isomorphism from which she survives further rounds.
Builds on
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments