AFTD Auto-Formalizing Theoretical Domains

op869_bounded_adversary_forces_unbounded

theoremverified

A winning post-degree-bounded t-fold adversary position also wins the same game without the post-degree restriction.

Statement

theorem op869_bounded_adversary_forces_unbounded {n : ℕ} (k t K D fuel i : ℕ)
    (P : Fin n → Finset (Fin n)) (C : Fin n → Finset ℕ)
    (h : op869_bounded_adversary_forces k t K D fuel i P C) :
    op869_adversary_forces k t K fuel i P C
Source
arXiv:2610.41516, Section 2.2, post-degree controlled adaptive t-fold coloring simulation.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • op869_bounded_adversary_forcesThe bounded t-fold adversary game is the t-fold game where, after each move, every vertex has post-degree at most D.
  • op869_adversary_forcesA bounded t-fold online-coloring adversary position is winning if, before the move budget or vertex indices run out, the adversary can…
  • 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.
  • 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…

The proof, explained

The proof proceeds by induction on the fuel parameter, generalizing over the vertex index and the configuration states. The unbounded adversary game has identical rules and winning conditions to the bounded game, except that the constraint bounding predecessor post-degrees by $D$ is removed. Consequently, the adversary can play the exact same predecessor set witness chosen in the bounded game, and any continuation either wins immediately or wins by the induction hypothesis.

  1. The theorem holds vacuously when $\mathrm{fuel} = 0$.

    We proceed by induction on $\mathrm{fuel}$, generalizing over the vertex index $i$ and the predecessor and coloring states $P$ and $C$. When $\mathrm{fuel} = 0$, the definition of $\mathrm{op869\_bounded\_adversary\_forces}$ is $\mathrm{False}$, so the hypothesis $h$ is contradictory.

    lines 5–6

      induction fuel generalizing i P C with
      | zero => simp [op869_bounded_adversary_forces] at h
  2. In the inductive step, we branch on whether $i < n$.

    For the induction step with fuel $\mathrm{fuel} + 1$, we split into cases depending on whether the current vertex index $i$ is within the graph bounds $i < n$.

    lines 7–8

      | succ fuel ih =>
        by_cases hi : i < n
  3. When $i < n$, both forcing conditions simplify to their one-step existential definitions.

    Using the condition $i < n$, the if-then-else conditionals in the definitions of $\mathrm{op869\_bounded\_adversary\_forces}$ and $\mathrm{op869\_adversary\_forces}$ evaluate to their positive branches via $\mathrm{dif\_pos}$.

    lines 9–10

    uses dif_pos

        · simp only [op869_bounded_adversary_forces, dif_pos hi] at h
          simp only [op869_adversary_forces, dif_pos hi]
  4. The winning move $S$ for the bounded adversary also serves as a winning move for the unbounded adversary.

    From hypothesis $h$, we extract a predecessor set $S$ of vertices before $i$ such that the updated graph is $k$-colorable, the post-degrees are bounded by $D$, and any valid response by the solver leads to a win or continuation. We provide this same $S$ as the witness for the unbounded game, retaining predecessor validity and $k$-colorability while discarding the degree bound.

    lines 11–12

          obtain ⟨S, hS, hcolor, hdegree, hnext⟩ := h
          refine ⟨S, hS, hcolor, ?_⟩
  5. Every response by the solver is either an immediate win or transitions to a winning position for the unbounded game.

    Let $c$ be a set of $t$ colors disjoint from $C(a)$ for all $a \in S$. The hypothesis on $S$ guarantees that $c$ either achieves total union cardinality at least $K$ (an immediate win, concluded with $\mathrm{Or.inl}$) or yields a winning bounded-adversary continuation with remaining fuel. In the latter case, we apply the induction hypothesis $\mathrm{ih}$ at step $i + 1$ to obtain a winning unbounded-adversary continuation, concluding with $\mathrm{Or.inr}$.

    lines 13–16

    uses Or.inl, Or.inr

          intro c hc hvalid
          rcases hnext c hc hvalid with hwin | hgame
          · exact Or.inl hwin
          · exact Or.inr (ih (i + 1) _ _ hgame)
  6. The case $i \ge n$ is impossible.

    When $i \ge n$, the definition of $\mathrm{op869\_bounded\_adversary\_forces}$ evaluates to $\mathrm{False}$, which contradicts the hypothesis $h$.

    line 17

        · simp [op869_bounded_adversary_forces, hi] at h
dif_pos
In a dependent if-then-else expression, if the condition holds, the expression evaluates to the positive branch.
Or.inl
From a proof of $a$, yields a proof of the disjunction $a ∨ b$.
Or.inr
From a proof of $b$, yields a proof of the disjunction $a ∨ b$.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem op869_bounded_adversary_forces_unbounded {n : ℕ} (k t K D fuel i : ℕ)    (P : Fin n → Finset (Fin n)) (C : Fin n → Finset ℕ)    (h : op869_bounded_adversary_forces k t K D fuel i P C) :    op869_adversary_forces k t K fuel i P C := by  induction fuel generalizing i P C with  | zero => simp [op869_bounded_adversary_forces] at h  | succ fuel ih =>    by_cases hi : i < n    · simp only [op869_bounded_adversary_forces, dif_pos hi] at h      simp only [op869_adversary_forces, dif_pos hi]      obtain ⟨S, hS, hcolor, hdegree, hnext⟩ := h      refine ⟨S, hS, hcolor, ?_⟩      intro c hc hvalid      rcases hnext c hc hvalid with hwin | hgame      · exact Or.inl hwin      · exact Or.inr (ih (i + 1) _ _ hgame)    · simp [op869_bounded_adversary_forces, hi] at h
See it in the graphDiscuss this resultChallenge it