While this submission is a draft, it cannot be used by other submissions.

The bijective pebble game

Lax119563.PebbleGame · concepts/Lax119563/PebbleGame.lean · lax-119563

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.

    Natural Language Statement

    Definition

    Let G,HG, H be colored graphs and m≥1m \geq 1. The bijective mm-pebble game BPm(G,H)\mathrm{BP}_m(G, H) is played by two players, Spoiler and Duplicator, with mm pairs of pebbles. A game state is a partial map SS assigning to some pebble indices i∈[m]i \in [m] a pair S(i)=(pi,qi)∈V(G)×V(H)S(i) = (p_i, q_i) \in V(G) \times V(H). The game starts in the empty game state. If ∣V(G)∣≠∣V(H)∣|V(G)| \neq |V(H)|, Spoiler wins immediately. Otherwise, each round consists of the following steps:

    1. Spoiler chooses i∈[m]i \in [m] and lifts the ii-th pebble pair.
    2. Duplicator chooses a bijection f ⁣:V(G)→V(H)f \colon V(G) \to V(H).
    3. Spoiler chooses p∈V(G)p \in V(G) and places the ii-th pebble pair on pp and f(p)f(p), i.e., sets S(i)=(p,f(p))S(i) = (p, f(p)).

    Spoiler wins after a round if the map pi↦qip_i \mapsto q_i, for the placed pairs S(i)=(pi,qi)S(i) = (p_i, q_i), is not a partial isomorphism: for all placed i,ji, j we need pi=pj  ⟺  qi=qjp_i = p_j \iff q_i = q_j, pipj∈E(G)  ⟺  qiqj∈E(H)p_i p_j \in E(G) \iff q_i q_j \in E(H), and χG(pi)=χH(qi)\chi_G(p_i) = \chi_H(q_i).

    For r≥0r \geq 0, Spoiler wins within rr rounds if he has a strategy that wins after one of the first rr rounds against every strategy of Duplicator; otherwise Duplicator survives rr rounds. Duplicator wins BPm(G,H)\mathrm{BP}_m(G, H) if she survives rr rounds for every rr.

    Concept map
    2 concepts; 3 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.Logic.Equiv.Fin.Basic
    2import Lax119563.ColoredGraphs
    3
    4/-!
    5---
    6title: The bijective pebble game
    7type: definition
    8---
    9Let G,HG, H be colored graphs and m≥1m \geq 1. The *bijective mm-pebble game*
    10BPm(G,H)\mathrm{BP}_m(G, H) is played by two players, Spoiler and Duplicator, with mm pairs of
    11pebbles. A *game state* is a partial map SS assigning to some pebble indices i∈[m]i \in [m] a
    12pair S(i)=(pi,qi)∈V(G)×V(H)S(i) = (p_i, q_i) \in V(G) \times V(H). The game starts in the empty game state. If
    13∣V(G)∣≠∣V(H)∣|V(G)| \neq |V(H)|, Spoiler wins immediately. Otherwise, each round consists of the
    14following steps:
    15
    161. Spoiler chooses i∈[m]i \in [m] and lifts the ii-th pebble pair.
    172. Duplicator chooses a bijection f ⁣:V(G)→V(H)f \colon V(G) \to V(H).
    183. Spoiler chooses p∈V(G)p \in V(G) and places the ii-th pebble pair on pp and f(p)f(p), i.e.,
    19 sets S(i)=(p,f(p))S(i) = (p, f(p)).
    20
    21Spoiler wins after a round if the map pi↦qip_i \mapsto q_i, for the placed pairs
    22S(i)=(pi,qi)S(i) = (p_i, q_i), is not a partial isomorphism: for all placed i,ji, j we need
    23pi=pj  ⟺  qi=qjp_i = p_j \iff q_i = q_j, pipj∈E(G)  ⟺  qiqj∈E(H)p_i p_j \in E(G) \iff q_i q_j \in E(H), and
    24χG(pi)=χH(qi)\chi_G(p_i) = \chi_H(q_i).
    25
    26For r≥0r \geq 0, Spoiler *wins within rr rounds* if he has a strategy that wins after one of
    27the first rr rounds against every strategy of Duplicator; otherwise Duplicator *survives rr
    28rounds*. Duplicator *wins* BPm(G,H)\mathrm{BP}_m(G, H) if she survives rr rounds for every rr.
    29
    30# Implementation notes
    31
    32Survival is defined by recursion on the number of remaining rounds: Duplicator survives
    33r+1r + 1 rounds from a state if, for every pebble index Spoiler may lift, she has a
    34bijection such that every placement yields a partial isomorphism from which she survives
    35rr further rounds.
    36-/
    37
    38open Lax119563.ColoredGraphs
    39
    40namespace Lax119563.PebbleGame
    41
    42/-- A game state of the `m`-pebble game: the pebble pairs currently placed. -/
    43abbrev 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. -/
    46def 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`. -/
    51def 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. -/
    58def 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. -/
    62def SpoilerWinsWithin (m r : ℕ) (G H : ColoredGraph) : Prop :=
    63 ¬ DuplicatorSurvives m r G H
    64
    65/-- Duplicator wins `BP_m(G, H)`. -/
    66def DuplicatorWins (m : ℕ) (G H : ColoredGraph) : Prop :=
    67 ∀ r, DuplicatorSurvives m r G H
    68
    69end Lax119563.PebbleGame
    70

    Implementation notes

    Survival is defined by recursion on the number of remaining rounds: Duplicator survives r+1r + 1 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 rr further rounds.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…