AFTD Auto-Formalizing Theoretical Domains

three_token_k2n_assemble_layer_cover

theoremverified

If the explicit candidate family has the claimed cardinality and dominates every configuration in each of the three possible left-token layers, it is a dominating set of the claimed size.

Statement

theorem three_token_k2n_assemble_layer_cover (n : ℕ) (hn : 4 ≤ n)
    (hcard : (three_token_k2n_explicit_family n hn).card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2)
    (hlayer : ∀ k ≤ 2, ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3},
      three_token_k2n_left_count z = k →
      z ∈ three_token_k2n_explicit_family n hn ∨ ∃ w ∈ three_token_k2n_explicit_family n hn,
        (token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3).Adj w z) :
    ∃ S : Finset {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3},
      simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3) (S : Set _) ∧
      S.card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2
Source
Explicit construction for three_token_k2n_has_dominating_set and OP-666.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • three_token_k2n_explicit_familyThe candidate family of three-token configurations: all configurations with left vertex 0 and a same-half pair on the right, the…
  • three_token_k2n_left_countThe number of left-part vertices in a three-token configuration.
  • three_token_k2n_left_count_le_twoEvery three-token configuration over Fin 2 plus Fin n contains at most two vertices from the left part.
  • token_graphThe k-token graph F_k(G) of a simple graph G has as vertices the k-subsets of V(G), with two k-subsets adjacent whenever their symmetric…
  • simple_graph_is_dominatingA subset S of vertices in a simple graph G is a dominating set if every vertex of G is in S or is adjacent to a vertex in S.
Used by 1

The proof, explained

The proof establishes the existence of the required dominating set by taking the candidate family `three_token_k2n_explicit_family n hn` as an explicit witness. Its size bound holds directly by the hypothesis `hcard`. To show domination, any 3-token configuration `z` has at most 2 tokens on the 2-element left side, so the layer-domination hypothesis `hlayer` applies directly to dominate `z`.

  1. It suffices to show that the explicit family is a dominating set.

    We witness the existential statement with the candidate family `three_token_k2n_explicit_family n hn`. Its cardinality satisfies the required bound directly by the hypothesis `hcard`, leaving only the requirement that it dominates the 3-token graph.

    line 10

      refine ⟨three_token_k2n_explicit_family n hn, ?_, hcard⟩
  2. The candidate family dominates every 3-token configuration z.

    By definition, a set is dominating if every vertex is either in the set or adjacent to an element of the set. For an arbitrary configuration `z`, the number of tokens it places on the left partition (of size 2) is at most 2 by `three_token_k2n_left_count_le_two`. Instantiating the hypothesis `hlayer` at this left-token count and configuration `z` (with `rfl` verifying the count equality) establishes that `z` is dominated by the family.

    lines 11–12

    uses three_token_k2n_left_count_le_two

      intro z
      exact hlayer (three_token_k2n_left_count z) (three_token_k2n_left_count_le_two z) z rfl
three_token_k2n_left_count_le_two
In any 3-token configuration on the bipartite graph with left part Fin 2, the number of tokens on the left is at most 2.

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 three_token_k2n_assemble_layer_cover (n : ℕ) (hn : 4 ≤ n)    (hcard : (three_token_k2n_explicit_family n hn).card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2)    (hlayer : ∀ k ≤ 2, ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3},      three_token_k2n_left_count z = k →      z ∈ three_token_k2n_explicit_family n hn ∨ ∃ w ∈ three_token_k2n_explicit_family n hn,        (token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3).Adj w z) :    ∃ S : Finset {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3},      simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3) (S : Set _) ∧      S.card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2 := by  refine ⟨three_token_k2n_explicit_family n hn, ?_, hcard⟩  intro z  exact hlayer (three_token_k2n_left_count z) (three_token_k2n_left_count_le_two z) z rfl
See it in the graphDiscuss this resultChallenge it