op869_bounded_fuel_mono
Increasing the number of remaining moves preserves a winning position in the bounded online coloring adversary game.
Statement
theorem op869_bounded_fuel_mono {n : ℕ} (k t K D : ℕ) (fuel fuel' i : ℕ) (P : Fin n → Finset (Fin n)) (C : Fin n → Finset ℕ) (hle : fuel ≤ fuel') (h : op869_bounded_adversary_forces k t K D fuel i P C) : op869_bounded_adversary_forces k t K D fuel' i P C- Source
- A monotonicity step in the finite online coloring game for arXiv:2610.41516, Section 2.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_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.
The proof, explained
The theorem is proved by induction on fuel, generalizing over all other game parameters. The base case fuel = 0 is vacuous because the adversary cannot force a win with zero fuel by definition. In the inductive step with fuel + 1, the target fuel fuel' must also be non-zero (fuel' = fuel'' + 1 with fuel ≤ fuel''). The adversary chooses the same predecessor set S as in the original strategy; against any valid coloring chosen by the painter, either the adversary wins immediately by reaching K colors, or the induction hypothesis applies to the continuation game since fuel ≤ fuel''.
The claim holds vacuously when the initial fuel is zero.
We induct on fuel, generalizing over fuel', i, P, and C. When fuel = 0, the definition of op869_bounded_adversary_forces evaluates directly to False. The hypothesis h is therefore contradictory, closing the base case.
induction fuel generalizing fuel' i P C with | zero => simp [op869_bounded_adversary_forces] at h
In the inductive step, the target fuel fuel' must be strictly positive.
In the step for fuel + 1, we consider the cases of fuel'. If fuel' = 0, the inequality fuel + 1 ≤ fuel' becomes fuel + 1 ≤ 0, which is impossible for natural numbers; linear arithmetic (omega) closes this branch.
| succ fuel ih => cases fuel' with | zero => omegaWhen the vertex index is within bounds (i < n), the adversary can reuse the winning predecessor set S.
Writing fuel' as fuel'' + 1, we case split on whether i < n. When i < n, rewriting with dif_pos unfolds the definition of op869_bounded_adversary_forces in both the hypothesis h and the goal. The hypothesis h yields a predecessor set S that satisfies the index condition, preserves k-colorability, and satisfies the post-degree bound D. We use this same S as the witness for fuel' + 1.
uses
dif_pos| succ fuel' => by_cases hi : i < n · simp only [op869_bounded_adversary_forces, dif_pos hi] at h ⊢ obtain ⟨S, hS, hcolor, hdegree, hnext⟩ := h refine ⟨S, hS, hcolor, hdegree, ?_⟩For any valid coloring response, the adversary either wins immediately or wins by the induction hypothesis.
For any valid set c of t colors disjoint from the colors of S, the hypothesis provides two possibilities: either the total number of colors used reaches the threshold K, or the position remains winning at vertex i + 1 with fuel moves remaining. In the former case, the adversary wins immediately via Or.inl. In the latter case, since fuel + 1 ≤ fuel'' + 1 implies fuel ≤ fuel'' by linear arithmetic (omega), the induction hypothesis applies to show that the continuation is also winning with fuel'' moves, giving the second disjunct via Or.inr.
uses
Or.inl,Or.inrintro c hc hvalid rcases hnext c hc hvalid with hw | hrec · exact Or.inl hw · exact Or.inr (ih fuel' (i+1) _ _ (by omega) hrec)
The case where the vertex index is out of bounds (i ≥ n) is contradictory.
When i ≥ n, the definition of op869_bounded_adversary_forces evaluates to False in the else-branch of the conditional. Simplifying the hypothesis h with ¬(i < n) produces False, closing this branch.
· simp [op869_bounded_adversary_forces, hi] at h
dif_pos- If a proposition c holds, then the dependent conditional if c then t else e evaluates to the then-branch t.
Or.inl- Given a proof of A, constructs a proof of the disjunction A ∨ B.
Or.inr- Given a proof of B, constructs a proof of the disjunction A ∨ B.
- The fuel parameter is an auxiliary counter used to ensure structural termination in Lean's definition of the multi-round game; on paper, the game simply ends once all n vertices have been processed.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem op869_bounded_fuel_mono {n : ℕ} (k t K D : ℕ) (fuel fuel' i : ℕ) (P : Fin n → Finset (Fin n)) (C : Fin n → Finset ℕ) (hle : fuel ≤ fuel') (h : op869_bounded_adversary_forces k t K D fuel i P C) : op869_bounded_adversary_forces k t K D fuel' i P C := by induction fuel generalizing fuel' i P C with | zero => simp [op869_bounded_adversary_forces] at h | succ fuel ih => cases fuel' with | zero => omega | succ fuel' => by_cases hi : i < n · simp only [op869_bounded_adversary_forces, dif_pos hi] at h ⊢ obtain ⟨S, hS, hcolor, hdegree, hnext⟩ := h refine ⟨S, hS, hcolor, hdegree, ?_⟩ intro c hc hvalid rcases hnext c hc hvalid with hw | hrec · exact Or.inl hw · exact Or.inr (ih fuel' (i+1) _ _ (by omega) hrec) · simp [op869_bounded_adversary_forces, hi] at h