AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it