op869_bounded_adversary_forces
def
The bounded t-fold adversary game is the t-fold game where, after each move, every vertex has post-degree at most D.
Statement
def op869_bounded_adversary_forces {n : ℕ} (k t K D : ℕ) : ℕ → ℕ → (Fin n → Finset (Fin n)) → (Fin n → Finset ℕ) → Prop
- Source
- arXiv:2610.41516, Section 2.2, post-degree controlled adaptive t-fold coloring simulation.
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 2
- op869_graph_from_predecessorsThe simple graph on the ordered vertices Fin n whose edge from an earlier vertex a to a later vertex b exists exactly when a is in the…
- op869_predecessor_postdegreeThe post-degree of a vertex in an ordered predecessor presentation is the number of later vertices that list it as a predecessor.
- Used by 3
- op869_bounded_adversary_forces_unboundedA winning post-degree-bounded t-fold adversary position also wins the same game without the post-degree restriction.
- op869_bounded_adversary_one_vertexWhen n and k are positive, an isolated vertex forces t colors in the bounded t-fold game in one move, for every post-degree bound D.
- op869_bounded_fuel_monoIncreasing the number of remaining moves preserves a winning position in the bounded online coloring adversary game.
Lean source view module on GitHub
def op869_bounded_adversary_forces {n : ℕ} (k t K D : ℕ) : ℕ → ℕ → (Fin n → Finset (Fin n)) → (Fin n → Finset ℕ) → Prop | 0, _, _, _ => False | fuel + 1, i, P, C => if hi : i < n then ∃ S : Finset (Fin n), (∀ a ∈ S, a.val < i) ∧ let v : Fin n := ⟨i, hi⟩ let P' := Function.update P v S (op869_graph_from_predecessors P').Colorable k ∧ (∀ a, op869_predecessor_postdegree P' a ≤ D) ∧ ∀ c : Finset ℕ, c.card = t → (∀ a ∈ S, Disjoint (C a) c) → let C' := Function.update C v c K ≤ ((Finset.univ.filter (fun a : Fin n => a.val ≤ i)).biUnion C').card ∨ op869_bounded_adversary_forces k t K D fuel (i + 1) P' C' else False