AFTD Auto-Formalizing Theoretical Domains

op869_bounded_adversary_one_vertex

theoremverified

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.

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

    lines 3–4

    uses op869_bounded_adversary_forces, dif_pos

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

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

    lines 11–15

    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]
  4. 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.

    lines 16–23

    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.

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