AFTD Auto-Formalizing Theoretical Domains

op869_adversary_forces_sound

theoremverified

A winning one-fold adversary position, whose recorded earlier colors agree with a proper online algorithm on the current predecessor graph, gives a k-colorable graph on which that algorithm uses at least K colors.

Statement

theorem op869_adversary_forces_sound {n : ℕ} (k K : ℕ)
    (A : SimpleGraph (Fin n) → Fin n → ℕ)
    (hA : IsOnlineColoringAlg A) (hproper : ProperlyColorsKColorable k A)
    (fuel i : ℕ) (P : Fin n → Finset (Fin n)) (C : Fin n → Finset ℕ)
    (hplay : op869_adversary_forces k 1 K fuel i P C)
    (hinv : ∀ a : Fin n, a.val < i → C a = {A (op869_graph_from_predecessors P) a}) :
    ∃ G : SimpleGraph (Fin n), G.Colorable k ∧ K ≤ colorsUsed (A G)
Source
arXiv:2610.41516, Sections 1 and 2; formal infrastructure for the adaptive online-coloring construction.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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_causalityIf two predecessor presentations agree through vertex i, any online coloring algorithm gives vertex i the same color on both graphs.
  • 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…
  • IsOnlineColoringAlgA deterministic coloring algorithm A : SimpleGraph (Fin n) → (Fin n → ℕ) assigning natural number colors to vertices of graphs on Fin n is…
  • ProperlyColorsKColorableFor an integer k and graph size n, a coloring algorithm A : SimpleGraph (Fin n) → (Fin n → ℕ) assigning natural number colors properly…
  • colorsUsedThe number of distinct colors assigned by a vertex coloring c : Fin n → ℕ is the cardinality of the image of c on Finset.univ.

The proof, explained

The proof proceeds by induction on the fuel parameter of the adversary forcing relation. In each round i < n, the adversary provides a predecessor neighborhood S for the new vertex v = i such that the updated graph G remains k-colorable. By the causality of online coloring algorithms, the colors assigned to earlier vertices are unchanged, and because the algorithm is proper on k-colorable graphs, its color on v must be disjoint from those of all neighbors in S. The adversary's response condition then guarantees that either the algorithm has already used at least K colors on the prefix up to i, or the adversary continues to force a win in the remaining rounds, which succeeds by the induction hypothesis.

  1. The base case holds: with zero fuel, the adversary hypothesis is contradictory.

    We proceed by induction on fuel, generalizing the current vertex index i, the predecessor map P, and the recorded color assignments C. When fuel = 0, the adversary forcing predicate op869_adversary_forces evaluates to False by definition, which contradicts the hypothesis hplay and closes the base case.

    lines 8–9

    uses op869_adversary_forces

      induction fuel generalizing i P C with
      | zero => simp [op869_adversary_forces] at hplay
  2. In the inductive step with i < n, the adversary provides a neighborhood S for vertex v = i such that the updated graph G is k-colorable.

    Assuming the result holds for smaller fuel, we split on whether i < n. In the active case i < n, unfolding op869_adversary_forces using dif_pos yields a predecessor set S ⊆ {0, …, i - 1} for vertex v = ⟨i, hi⟩ such that updating P at v to S produces a k-colorable graph G, along with a response property hnext for any valid singleton color assigned to v.

    lines 10–16

    uses op869_adversary_forces, dif_pos

      | succ fuel ih =>
        by_cases hi : i < n
        · simp only [op869_adversary_forces, dif_pos hi] at hplay
          obtain ⟨S, hS, hcolor, hnext⟩ := hplay
          let v : Fin n := ⟨i, hi⟩
          let P' := Function.update P v S
          let G := op869_graph_from_predecessors P'
  3. For every vertex a < i, the algorithm's color on a in the new graph G agrees with the recorded color C(a).

    By the induction invariant hinv, C(a) is the singleton containing the algorithm's color on a in the predecessor graph of P. Updating P at v = i only alters the predecessor set of vertex i. Since any j ≤ a satisfies j < i and thus j ≠ v, the predecessor assignments P and P' agree on all vertices up to a. By causality of the online coloring algorithm (op869_predecessor_causality), A assigns the same color to a in G as in the predecessor graph of P.

    lines 17–27

    uses op869_predecessor_causality, congrArg, Fin.val, Ne.symm

          have hbefore (a : Fin n) (ha : a.val < i) : C a = {A G a} := by
            rw [hinv a ha]
            congr 1
            apply op869_predecessor_causality A hA P P' a
            intro j hj
            have hj' : j.val ≤ a.val := hj
            have hjne : j ≠ v := by
              intro h
              have heq : j.val = i := congrArg Fin.val h
              omega
            simp [P', hjne, Ne.symm hjne]
  4. The color c = {A(G)(v)} chosen by the algorithm for vertex v is disjoint from the recorded colors of all predecessors in S.

    For each predecessor a ∈ S, we have a < v and a ∈ P'(v), so a and v are adjacent in G by definition of the graph from predecessors. Because G is k-colorable and A is a proper coloring algorithm on k-colorable graphs (hproper), A(G)(a) ≠ A(G)(v). Using C(a) = {A(G)(a)} from the previous step, the singletons C(a) and c are disjoint by Finset.disjoint_singleton.mpr.

    lines 28–35

    uses op869_graph_from_predecessors, Or.inl, Finset.disjoint_singleton.mpr

          let c : Finset ℕ := {A G v}
          have hc : ∀ a ∈ S, Disjoint (C a) c := by
            intro a ha
            have hlt : a < v := hS a ha
            have hadj : G.Adj a v := by
              exact Or.inl ⟨hlt, by simp [G, P', op869_graph_from_predecessors, ha]⟩
            rw [hbefore a (hS a ha)]
            exact Finset.disjoint_singleton.mpr (hproper G hcolor a v hadj)
  5. The updated color record C' satisfies C'(a) = {A(G)(a)} for all vertices a ≤ i.

    Let C' update C at v to c. For a ≤ i, either a < i or a = i. If a < i, then a ≠ v, so C'(a) = C(a) = {A(G)(a)} by the earlier invariance. If a = i, then a = v, so C'(a) = c = {A(G)(v)} by definition.

    lines 36–46

    uses lt_or_eq_of_le, congrArg, Fin.val, Ne.symm, Fin.ext

          let C' := Function.update C v c
          have hprefix (a : Fin n) (ha : a.val ≤ i) : C' a = {A G a} := by
            rcases lt_or_eq_of_le ha with ha | ha
            · have hne : a ≠ v := by
                intro h
                have heq : a.val = i := congrArg Fin.val h
                omega
              simpa [C', hne, Ne.symm hne] using hbefore a ha
            · have heq : a = v := Fin.ext ha
              subst a
              simp [C', c]
  6. If the adversary's response condition guarantees at least K colors on the prefix up to i, then G witnesses the theorem.

    Since c is a singleton disjoint from each C(a) for a ∈ S, the adversary's response branching hnext applies. In the first branch, at least K distinct colors appear in the union of C'(a) over all a ≤ i. Since each C'(a) is {A(G)(a)}, every such color lies in the image of A(G) over all vertices. Monotonicity of finite set cardinality (Finset.card_le_card) implies K ≤ colorsUsed(A(G)). Combined with G being k-colorable, G satisfies the existential goal.

    lines 47–58

    uses le_trans, colorsUsed, Finset.card_le_card, Finset.mem_biUnion.mp, Finset.mem_filter.mp, Finset.mem_singleton.mp, Finset.mem_image.mpr, Finset.mem_univ

          rcases hnext c (by simp [c]) hc with hK | hgame
          · refine ⟨G, hcolor, ?_⟩
            apply le_trans hK
            unfold colorsUsed
            apply Finset.card_le_card
            intro x hx
            obtain ⟨a, ha, hx⟩ := Finset.mem_biUnion.mp hx
            have ha' : a.val ≤ i := (Finset.mem_filter.mp ha).2
            change x ∈ C' a at hx
            rw [hprefix a ha'] at hx
            have heq : x = A G a := Finset.mem_singleton.mp hx
            exact Finset.mem_image.mpr ⟨a, Finset.mem_univ _, heq.symm⟩
  7. If the adversary continues the game at step i + 1, the induction hypothesis applies.

    In the second branch of hnext, the adversary forces a win with one less unit of fuel at index i + 1, using updated predecessor map P' and color assignments C'. The invariant at round i + 1 requires C'(a) = {A(G)(a)} for all a < i + 1, which is equivalent to a ≤ i and holds by the prefix property established in Step 5. The induction hypothesis ih directly produces the desired graph.

    lines 59–61

          · apply ih (i + 1) P' C' hgame
            intro a ha
            exact hprefix a (by omega)
  8. The case i ≥ n is contradictory.

    When i ≥ n, the adversary predicate op869_adversary_forces evaluates to False, contradicting hplay.

    line 62

    uses op869_adversary_forces

        · simp [op869_adversary_forces, hi] at hplay
op869_adversary_forces
The inductive predicate stating that an adversary can force an online coloring algorithm to use at least K colors within a given fuel bound.
dif_pos
A dependent if-then-else expression evaluates to its 'then' branch when the condition is proven to hold.
op869_predecessor_causality
An online coloring algorithm assigns the same color to vertex i in two graphs whenever their predecessor sets agree on all vertices up to i.
congrArg
Functions preserve equality: if a₁ = a₂, then f(a₁) = f(a₂).
Fin.val
The underlying natural number value of an element of Fin n.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
op869_graph_from_predecessors
The simple graph on Fin n where an edge connects a < b if and only if a is in the predecessor set of b.
Or.inl
Left introduction for disjunction: a implies a ∨ b.
Finset.disjoint_singleton.mpr
Two singleton sets {x} and {y} are disjoint if and only if x ≠ y.
lt_or_eq_of_le
In a partial order, a ≤ b implies a < b or a = b.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
colorsUsed
The number of distinct colors assigned by a coloring, defined as the cardinality of its image on all vertices.
Finset.card_le_card
If finite set s is a subset of finite set t, then |s| ≤ |t|.
Finset.mem_biUnion.mp
An element belongs to the union of a family of finite sets if and only if it belongs to one of the constituent sets.
Finset.mem_filter.mp
An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
Finset.mem_singleton.mp
If an element belongs to the singleton set {y}, then it equals y.
Finset.mem_image.mpr
If a ∈ s and f(a) = y, then y belongs to the image f(s).
Finset.mem_univ
Every element of a finite type belongs to the universal finite set univ.

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_adversary_forces_sound {n : ℕ} (k K : ℕ)    (A : SimpleGraph (Fin n) → Fin n → ℕ)    (hA : IsOnlineColoringAlg A) (hproper : ProperlyColorsKColorable k A)    (fuel i : ℕ) (P : Fin n → Finset (Fin n)) (C : Fin n → Finset ℕ)    (hplay : op869_adversary_forces k 1 K fuel i P C)    (hinv : ∀ a : Fin n, a.val < i → C a = {A (op869_graph_from_predecessors P) a}) :    ∃ G : SimpleGraph (Fin n), G.Colorable k ∧ K ≤ colorsUsed (A G) := by  induction fuel generalizing i P C with  | zero => simp [op869_adversary_forces] at hplay  | succ fuel ih =>    by_cases hi : i < n    · simp only [op869_adversary_forces, dif_pos hi] at hplay      obtain ⟨S, hS, hcolor, hnext⟩ := hplay      let v : Fin n := ⟨i, hi⟩      let P' := Function.update P v S      let G := op869_graph_from_predecessors P'      have hbefore (a : Fin n) (ha : a.val < i) : C a = {A G a} := by        rw [hinv a ha]        congr 1        apply op869_predecessor_causality A hA P P' a        intro j hj        have hj' : j.val ≤ a.val := hj        have hjne : j ≠ v := by          intro h          have heq : j.val = i := congrArg Fin.val h          omega        simp [P', hjne, Ne.symm hjne]      let c : Finset ℕ := {A G v}      have hc : ∀ a ∈ S, Disjoint (C a) c := by        intro a ha        have hlt : a < v := hS a ha        have hadj : G.Adj a v := by          exact Or.inl ⟨hlt, by simp [G, P', op869_graph_from_predecessors, ha]⟩        rw [hbefore a (hS a ha)]        exact Finset.disjoint_singleton.mpr (hproper G hcolor a v hadj)      let C' := Function.update C v c      have hprefix (a : Fin n) (ha : a.val ≤ i) : C' a = {A G a} := by        rcases lt_or_eq_of_le ha with ha | ha        · have hne : a ≠ v := by            intro h            have heq : a.val = i := congrArg Fin.val h            omega          simpa [C', hne, Ne.symm hne] using hbefore a ha        · have heq : a = v := Fin.ext ha          subst a          simp [C', c]      rcases hnext c (by simp [c]) hc with hK | hgame      · refine ⟨G, hcolor, ?_⟩        apply le_trans hK        unfold colorsUsed        apply Finset.card_le_card        intro x hx        obtain ⟨a, ha, hx⟩ := Finset.mem_biUnion.mp hx        have ha' : a.val ≤ i := (Finset.mem_filter.mp ha).2        change x ∈ C' a at hx        rw [hprefix a ha'] at hx        have heq : x = A G a := Finset.mem_singleton.mp hx        exact Finset.mem_image.mpr ⟨a, Finset.mem_univ _, heq.symm⟩      · apply ih (i + 1) P' C' hgame        intro a ha        exact hprefix a (by omega)    · simp [op869_adversary_forces, hi] at hplay
See it in the graphDiscuss this resultChallenge it