op869_bounded_adversary_one_vertex
When n and k are positive, an isolated vertex forces t colors in the bounded t-fold game in one move, for every post-degree bound D.
Statement
theorem op869_bounded_adversary_one_vertex {n k t D : ℕ} (hn : 0 < n) (hk : 0 < k) : op869_bounded_adversary_forces k t t D 1 0 (fun _ : Fin n => ∅) (fun _ : Fin n => ∅)
- 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 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_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 adversary plays vertex 0 as an isolated vertex by selecting an empty predecessor set S = ∅, which is valid since n > 0. The resulting graph has no edges, making it trivially k-colorable (as k > 0) with all vertex post-degrees equal to 0 ≤ D. When the player assigns any set of t colors to vertex 0, the union of assigned colors on the evaluated vertices contains that entire set, successfully forcing at least t colors in a single round.
The adversary chooses an empty predecessor set S = ∅ for vertex 0, reducing the goal to three verification obligations.
Unfolding the definition `op869_bounded_adversary_forces` for fuel 1 and vertex index 0, and evaluating the condition 0 < n using `dif_pos hn`, the adversary must provide a predecessor set S ⊆ Fin n whose elements are strictly smaller than 0. Choosing S = ∅ vacuously satisfies this condition, leaving three requirements: the resulting graph is k-colorable, vertex post-degrees are bounded by D, and any choice of t colors by the player forces at least t colors overall.
uses
op869_bounded_adversary_forces,dif_possimp only [op869_bounded_adversary_forces, dif_pos hn] refine ⟨∅, by simp, ?_, ?_, ?_⟩
The graph with no predecessor edges is k-colorable.
Since k > 0, we define a candidate k-coloring by assigning the color 0 to every vertex via `SimpleGraph.Coloring.mk`. To verify that this is a valid coloring, assume for contradiction that two vertices a and b are adjacent (`hadj`). Because updating the empty predecessor map with ∅ leaves it identically empty (`hempty`), the graph defined by `op869_graph_from_predecessors` contains no edges, yielding a contradiction.
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
Every vertex has predecessor post-degree at most D.
For an arbitrary vertex a, rewriting the predecessor map to the identically empty function shows that no vertex lists a as a predecessor. Thus the post-degree computed by `op869_predecessor_postdegree` is 0, which is at most D.
uses
op869_predecessor_postdegree· intro a have hempty : Function.update (fun _ : Fin n => (∅ : Finset (Fin n))) ⟨0, hn⟩ ∅ = (fun _ => ∅) := by funext x; simp rw [hempty] simp [op869_predecessor_postdegree]
Any player assignment of t colors to vertex 0 forces at least t total colors.
Let c be the set of t colors chosen by the player for vertex 0 (`hc`). Choosing the left disjunct of the game outcome asserts that at least t colors have already been forced. Vertex 0 satisfies 0 ≤ 0, so it belongs to the filtered set of evaluated vertices (`hmem`). Since vertex 0 is assigned the color set c, every color x ∈ c belongs to the union of assigned color sets via `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
Finset.mem_biUnion.mpr- An element belongs to the indexed union ⋃_{a ∈ s} t(a) if it belongs to t(a) for some a ∈ s.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then the cardinality of s is at most the cardinality of t.
SimpleGraph.Coloring.mk- Constructs a proper graph coloring from a vertex color assignment and a proof that adjacent vertices receive distinct colors.
dif_pos- In a dependent if-then-else (`dite c t e`), if the condition c is true, the expression evaluates to the positive branch.
op869_bounded_adversary_forces- The game predicate stating that the adversary can force the player to use at least a target number of colors within a given number of rounds, subject to k-colorability and post-degree bounds.
op869_graph_from_predecessors- The simple graph on Fin n whose edges connect pairs a < b where a belongs to the predecessor set of b.
op869_predecessor_postdegree- The post-degree of vertex a, defined as the number of vertices b > a that have a in their predecessor set.
- The equality `Function.update (fun _ => ∅) ⟨0, hn⟩ ∅ = fun _ => ∅` is proved inline via function extensionality (`funext`) and simplification in both the colorability check (lines 7–8) and the post-degree check (lines 12–13).
- The player's disjointness hypothesis `∀ a ∈ S, Disjoint (C a) c` is discarded on line 16 because the predecessor set S is empty, making the condition vacuous.
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_adversary_one_vertex {n k t D : ℕ} (hn : 0 < n) (hk : 0 < k) : op869_bounded_adversary_forces k t t D 1 0 (fun _ : Fin n => ∅) (fun _ : Fin n => ∅) := by simp only [op869_bounded_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 a have hempty : Function.update (fun _ : Fin n => (∅ : Finset (Fin n))) ⟨0, hn⟩ ∅ = (fun _ => ∅) := by funext x; simp rw [hempty] simp [op869_predecessor_postdegree] · 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