arrows_tree_grundy
The Grundy value of the Game of Arrows on a finite simple graph G is the Grundy value of the empty position ArrowsEmptyPos V at fuel (Fintype.card V * Fintype.card V).
Statement
noncomputable def arrows_tree_grundy {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ
- Defined in
- arXiv:2610.15145 Section 2.2
- Verified
- 24 Oct 2026
- Axioms
- none listed
- Built on 3
- ArrowsPosGiven a type V, ArrowsPos V is the subtype of boolean-valued binary relations p : V → V → Bool that are asymmetric, meaning that for all…
- ArrowsEmptyPosThe empty starting position in ArrowsPos V whose boolean relation is everywhere false.
- arrows_pos_grundyThe Grundy value of a position p : ArrowsPos V in the Game of Arrows on G at recursion depth fuel, defined as 0 when fuel = 0 and as the…
- Used by 2
- arrows_parity_of_strategy_classLet T be a finite tree and S a class of positions of the Game of Arrows on T that contains the empty position, such that from every…
- arrows_realizable_grundy_valuesThe set of natural numbers g such that there exists a finite tree G (a simple graph G on a finite type V satisfying G.IsTree) with…
Read back from the Lean
arrows_tree_grundy defines a function that takes:
- a type V with decidable equality ([DecidableEq V]) and a finite instance ([Fintype V]), and
- a simple graph G : SimpleGraph V with decidable adjacency ([DecidableRel G.Adj]),
and returns the natural number computed by arrows_pos_grundy G (|V| * |V|) (ArrowsEmptyPos V). That is, it computes the Sprague-Grundy value of the "Arrows" game played on G starting from the empty position (no directed edges), using |V| * |V| as the recursion fuel.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The Grundy value of the empty position of the Game of Arrows on a finite graph G. -/ noncomputable def arrows_tree_grundy {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ := arrows_pos_grundy G (Fintype.card V * Fintype.card V) (ArrowsEmptyPos V)