AFTD Auto-Formalizing Theoretical Domains

op869_adversary_one_vertex

theoremverified

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.

  1. 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.

    lines 3–4

    uses op869_adversary_forces, dif_pos

      simp only [op869_adversary_forces, dif_pos hn]
      refine ⟨∅, by simp, ?_, ?_⟩
  2. 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.

    lines 5–10

    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
  3. 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.

    lines 11–18

    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.

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_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
See it in the graphDiscuss this resultChallenge it