op869_adversary_forces
def
A bounded t-fold online-coloring adversary position is winning if, before the move budget or vertex indices run out, the adversary can choose earlier neighbors while maintaining a k-colorable graph and force at least K distinct colors against every legal t-element response; the recursive state also records previously assigned color sets.
Statement
def op869_adversary_forces {n : ℕ} (k t K : ℕ) : ℕ → ℕ → (Fin n → Finset (Fin n)) → (Fin n → Finset ℕ) → Prop
- Source
- arXiv:2610.41516, Sections 1 and 2; formal infrastructure for the adaptive online-coloring construction.
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 1
- 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…
- 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_adversary_forces_soundA winning one-fold adversary position, whose recorded earlier colors agree with a proper online algorithm on the current predecessor…
- op869_adversary_one_vertexFor any positive vertex and color bounds, a t-fold adversary can force t colors in one move from the empty position.
Lean source view module on GitHub
def op869_adversary_forces {n : ℕ} (k t K : ℕ) : ℕ → ℕ → (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 ∧ ∀ 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_adversary_forces k t K fuel (i + 1) P' C' else False