Assignment moves, pass moves, and deviations

Lax689614.RegularPlay · concepts/Lax689614/RegularPlay.lean · lax-689614

proven

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

    Theorem

    An assignment move is vitiv_it_i or vifiv_if_i with i<ni<n. A pass move is vitiv_it_i with ni<Rn\leq i<R, or yiziy_iz_i. A regular position is reachable from the initial graph by such moves. Write rr and kk for the numbers of surviving viv_i and yiy_i, respectively.

    Claim 7: when mm is odd, rmr\geq m, and k1k\geq1, any other move loses unless it is sajsa_j and all literal vertices of clause jj are gone. Claim 8: at a regular position with rmr\geq m, such an exceptional move wins exactly when r+kr+k is even.

    Concept map
    7 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax689614.Construction
    2import Lax689614.Grundy
    3
    4/-!
    5---
    6title: Assignment moves, pass moves, and deviations
    7type: theorem
    8---
    9An assignment move is vitiv_it_i or vifiv_if_i with i<ni<n. A pass move is
    10vitiv_it_i with ni<Rn\leq i<R, or yiziy_iz_i. A regular position is reachable
    11from the initial graph by such moves. Write rr and kk for the numbers
    12of surviving viv_i and yiy_i, respectively.
    13
    14Claim 7: when mm is odd, rmr\geq m, and k1k\geq1, any other move
    15loses unless it is sajsa_j and all literal vertices of clause jj are gone.
    16Claim 8: at a regular position with rmr\geq m, such an exceptional move
    17wins exactly when r+kr+k is even.
    18-/
    19
    20namespace Lax689614.RegularPlay
    21
    22open PositiveCNF Construction ArcKayles
    23
    24def SameEdge (u w x z : ℕ) : Prop := (u = x ∧ w = z) ∨ (u = z ∧ w = x)
    25
    26def RegularMove (φ : Formula) (u w : ℕ) : Prop :=
    27 (∃ i < R φ, SameEdge u w (v φ i) (vt φ i)) ∨
    28 (∃ i < φ.nvars, SameEdge u w (v φ i) (f φ i)) ∨
    29 (∃ i < K φ, SameEdge u w (y φ i) (z φ i))
    30
    31inductive Reachable (φ : Formula) : Finset ℕ → Prop
    32 | initial : Reachable φ (board φ)
    33 | step {S : Finset ℕ} {u w : ℕ} : Reachable φ S →
    34 u ∈ S → w ∈ S → (graph φ).Adj u w → RegularMove φ u w →
    35 Reachable φ (remove S u w)
    36
    37def remainingV (φ : Formula) (S : Finset ℕ) : ℕ :=
    38 ((Finset.range (R φ)).filter fun i => v φ i ∈ S).card
    39
    40def remainingY (φ : Formula) (S : Finset ℕ) : ℕ :=
    41 ((Finset.range (K φ)).filter fun i => y φ i ∈ S).card
    42
    43def Exhausted (φ : Formula) (S : Finset ℕ) (j : Fin φ.clauses.length) : Prop :=
    44 ∀ i ∈ φ.clauses[j], f φ i ∉ S
    45
    46def Exceptional (φ : Formula) (S : Finset ℕ) (u w : ℕ) : Prop :=
    47 ∃ j : Fin φ.clauses.length, SameEdge u w s (a φ j) ∧ Exhausted φ S j
    48
    49axiom deviation_loses (φ : Formula) (hm : φ.clauses.length % 2 = 1)
    50 (S : Finset ℕ) (hS : Reachable φ S)
    51 (hr : φ.clauses.length ≤ remainingV φ S) (hk : 1remainingY φ S)
    52 (u w : ℕ) (hu : u ∈ S) (hw : w ∈ S) (he : (graph φ).Adj u w)
    53 (hn : ¬ RegularMove φ u w) (hx : ¬ Exceptional φ S u w) :
    54 Winning (graph φ) (remove S u w)
    55
    56axiom exceptional_parity (φ : Formula) (hm : φ.clauses.length % 2 = 1)
    57 (S : Finset ℕ) (hS : Reachable φ S)
    58 (hr : φ.clauses.length ≤ remainingV φ S)
    59 (j : Fin φ.clauses.length) (hj : Exhausted φ S j) :
    60 ¬ Winning (graph φ) (remove S s (a φ j)) ↔
    61 (remainingV φ S + remainingY φ S) % 2 = 0
    62
    63end Lax689614.RegularPlay
    64
    Show ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

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

    Loading discussion…