ArrowsLegalMove
In a simple graph G, a transition from position p to q in ArrowsPos V is a legal move if there exist u, v with ArrowsUnmarked G p u v such that q.1 is obtained by updating p.1 to true at (u, v), and neither u nor v is a sink or a source in q.
Statement
def ArrowsLegalMove {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p q : ArrowsPos V) : Prop
- Defined in
- arXiv:2610.15145 Section 2.2
- Verified
- 24 Oct 2026
- Axioms
- none listed
- Built on 4
- 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…
- ArrowsUnmarkedIn a simple graph G and position p : ArrowsPos V, vertices u and v form an unmarked edge if G.Adj u v and both p.1 u v and p.1 v u are…
- ArrowsIsSinkIn a simple graph G and position p : ArrowsPos V, vertex u is a sink if G.degree u ≥ 1 and for every neighbor v adjacent to u in G, p.1 v…
- ArrowsIsSourceIn a simple graph G and position p : ArrowsPos V, vertex u is a source if G.degree u ≥ 1 and for every neighbor v adjacent to u in G, p.1…
- Used by 6
- arrows_pos_grundy_eq_mod_two_of_classStrategy lemma for parity in the Game of Arrows: let e be a function on positions that drops by exactly one along every legal move, and S…
- arrows_markable_unmarked_of_legalEvery legal move of the Game of Arrows decreases the number of unmarked markable edges by exactly one.
- 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_pos_grundy_options_finiteFor any fuel and position p of the Game of Arrows on a finite graph, the set of fuel-bounded Grundy values of the legal options of p is…
- 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…
- arrows_legal_move_decidableFor a finite graph with decidable equality and decidable adjacency, whether q is a legal option of p is decidable.
Read back from the Lean
For a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and two arrow configurations p and q (where an arrow configuration is a function V → V → Bool with no bidirectional arrows, i.e., ∀ a b, p a b → ¬ p b a):
ArrowsLegalMove G p q asserts that there exist vertices u, v : V such that:
1. u and v are adjacent in G, and the edge between them is unmarked in p (neither p.1 u v nor p.1 v u is true);
2. q is obtained from p by directing an edge from u to v (for all x, y : V, q.1 x y is true if x = u ∧ y = v, and p.1 x y otherwise);
3. u is not a sink in G under q;
4. u is not a source in G under q;
5. v is not a sink in G under q;
6. v is not a source in G under q.
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
/-- A move from position p to position q is legal if an unmarked edge uv is oriented as u -> v and neither endpoint becomes a sink or source in q. -/ def ArrowsLegalMove {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p q : ArrowsPos V) : Prop := ∃ u v, ArrowsUnmarked G p u v ∧ (∀ x y, q.1 x y = if x = u ∧ y = v then true else p.1 x y) ∧ ¬ ArrowsIsSink G q u ∧ ¬ ArrowsIsSource G q u ∧ ¬ ArrowsIsSink G q v ∧ ¬ ArrowsIsSource G q v