op869_adversary_forces_sound
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.
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.
uses
op869_adversary_forcesinduction fuel generalizing i P C with | zero => simp [op869_adversary_forces] at hplay
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.
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'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.
uses
op869_predecessor_causality,congrArg,Fin.val,Ne.symmhave 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]
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.
uses
op869_graph_from_predecessors,Or.inl,Finset.disjoint_singleton.mprlet 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)
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.
uses
lt_or_eq_of_le,congrArg,Fin.val,Ne.symm,Fin.extlet 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]
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.
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_univrcases 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⟩
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.
· apply ih (i + 1) P' C' hgame intro a ha exact hprefix a (by omega)
The case i ≥ n is contradictory.
When i ≥ n, the adversary predicate op869_adversary_forces evaluates to False, contradicting hplay.
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.
- The invariant C(a) = {A(G)(a)} records colors as singleton finite sets rather than bare numbers to interface with the general adversary predicate op869_adversary_forces instantiated at t = 1.
- The tactic omega discharges linear arithmetic contradictions on indices (for example, showing that j ≠ v when j ≤ a < i and v = i).
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_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