op869_adversary_one_vertex
For any positive vertex and color bounds, a t-fold adversary can force t colors in one move from the empty position.
Statement
theorem op869_adversary_one_vertex {n k t : ℕ} (hn : 0 < n) (hk : 0 < k) : op869_adversary_forces k t t 1 0 (fun _ : Fin n => ∅) (fun _ : Fin n => ∅)
- 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 2
- 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_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
To show that the adversary can force t colors in one move from the empty position, the adversary chooses an empty set of predecessors for the first vertex (index 0). Because the resulting graph has no edges, it is trivially k-colorable using a single color (since k > 0). When the player responds by assigning any set of t colors to vertex 0, the union of colors used on all vertices up to index 0 contains all of these t colors, immediately achieving the required bound of t colors.
The adversary chooses an empty predecessor set for vertex 0, reducing the goal to checking colorability and color forcing.
We unfold the definition of `op869_adversary_forces` for 1 round starting at vertex index 0. Because 0 < n, the conditional takes its positive branch via `dif_pos`. The adversary must present a predecessor set S for vertex 0 consisting only of vertices with strictly smaller index. Setting S = ∅ satisfies this condition vacuously, leaving two obligations: showing that the resulting graph is k-colorable, and showing that any response by the player yields at least t colors.
uses
op869_adversary_forces,dif_possimp only [op869_adversary_forces, dif_pos hn] refine ⟨∅, by simp, ?_, ?_⟩
The graph with empty predecessor sets is k-colorable.
Because k > 0, we can assign every vertex the constant color 0 using `SimpleGraph.Coloring.mk`. To confirm this coloring is proper, we must check that no two adjacent vertices share a color. Updating the identically empty predecessor function with ∅ at vertex 0 leaves all predecessor sets empty (`hempty`). In `op869_graph_from_predecessors`, an edge requires one vertex to be in the predecessor set of the other; with all predecessor sets empty, the graph has no edges at all, so the adjacency assumption (`hadj`) simplifies to False.
uses
SimpleGraph.Coloring.mk,op869_graph_from_predecessors· refine ⟨SimpleGraph.Coloring.mk (fun _ => ⟨0, hk⟩) ?_⟩ intro a b hadj have hempty : Function.update (fun _ : Fin n => (∅ : Finset (Fin n))) ⟨0, hn⟩ ∅ = (fun _ => ∅) := by funext x; simp rw [hempty] at hadj simp [op869_graph_from_predecessors] at hadj
Any valid choice of t colors for vertex 0 forces at least t colors in total.
Let c be any set of t colors chosen by the player for vertex 0. We take the left alternative of the disjunction, which asserts that the total number of colors used on vertices with index ≤ 0 is at least t. Vertex 0 belongs to the set of vertices with index ≤ 0 (`hmem`), and vertex 0 is assigned the color set c. Thus, every element of c belongs to the union of color sets across vertices ≤ 0 by `Finset.mem_biUnion.mpr`, establishing c ⊆ ⋃_{a ≤ 0} C'(a) (`hsub`). By monotonicity of cardinality (`Finset.card_le_card`), the union has size at least |c| = t.
uses
Finset.mem_biUnion.mpr,Finset.card_le_card· intro c hc _ left have hmem : (⟨0, hn⟩ : Fin n) ∈ Finset.univ.filter (fun a : Fin n => a.val ≤ 0) := by simp have hsub : c ⊆ (Finset.univ.filter (fun a : Fin n => a.val ≤ 0)).biUnion (Function.update (fun _ : Fin n => (∅ : Finset ℕ)) ⟨0, hn⟩ c) := by intro x hx exact Finset.mem_biUnion.mpr ⟨⟨0, hn⟩, hmem, by simpa using hx⟩ simpa [hc] using Finset.card_le_card hsub
op869_adversary_forces- The predicate defining whether an adversary can force at least K colors in an online graph-coloring game within a specified number of rounds from a given state.
dif_pos- In a dependent if-then-else (`if h : c then t else e`), if the condition c holds with proof hc, the expression evaluates to t hc.
SimpleGraph.Coloring.mk- Constructs a valid graph coloring from a function assigning colors to vertices and a proof that adjacent vertices never receive the same color.
op869_graph_from_predecessors- The simple graph constructed from a predecessor map, where an undirected edge connects two vertices if and only if the smaller index belongs to the predecessor set of the larger.
Finset.mem_biUnion.mpr- An element x belongs to the indexed union ⋃_{a ∈ s} t(a) if there is some a ∈ s such that x ∈ t(a).
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most the cardinality of t.
- The definition `op869_adversary_forces` uses a fuel parameter to bound the game depth and provides a disjunction between achieving the target number of colors immediately or continuing recursively; here, with fuel 1, the adversary forces the target in the very first step, making the recursive alternative unused (`False`).
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_one_vertex {n k t : ℕ} (hn : 0 < n) (hk : 0 < k) : op869_adversary_forces k t t 1 0 (fun _ : Fin n => ∅) (fun _ : Fin n => ∅) := by simp only [op869_adversary_forces, dif_pos hn] refine ⟨∅, by simp, ?_, ?_⟩ · refine ⟨SimpleGraph.Coloring.mk (fun _ => ⟨0, hk⟩) ?_⟩ intro a b hadj have hempty : Function.update (fun _ : Fin n => (∅ : Finset (Fin n))) ⟨0, hn⟩ ∅ = (fun _ => ∅) := by funext x; simp rw [hempty] at hadj simp [op869_graph_from_predecessors] at hadj · intro c hc _ left have hmem : (⟨0, hn⟩ : Fin n) ∈ Finset.univ.filter (fun a : Fin n => a.val ≤ 0) := by simp have hsub : c ⊆ (Finset.univ.filter (fun a : Fin n => a.val ≤ 0)).biUnion (Function.update (fun _ : Fin n => (∅ : Finset ℕ)) ⟨0, hn⟩ c) := by intro x hx exact Finset.mem_biUnion.mpr ⟨⟨0, hn⟩, hmem, by simpa using hx⟩ simpa [hc] using Finset.card_le_card hsub