AFTD Auto-Formalizing Theoretical Domains

three_token_k2n_assemble_three_layers

theoremverified

If the explicit candidate family has the claimed cardinality and dominates each of the layers with zero, one and two left-part tokens, the required dominating set exists.

Statement

theorem three_token_k2n_assemble_three_layers (n : ℕ) (hn : 4 ≤ n)
    (hcard : (three_token_k2n_explicit_family n hn).card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2)
    (h0 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 0 →
      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)
    (h1 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 1 →
      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)
    (h2 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 2 →
      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_assemble_layer_coverIf the explicit candidate family has the claimed cardinality and dominates every configuration in each of the three possible left-token…
  • 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.

The proof, explained

The proof reduces the existence of the desired dominating set to verifying that the explicit candidate family dominates every 3-token configuration having at most two tokens on the left part of $K_{2, n}$, using the assembly lemma `three_token_k2n_assemble_layer_cover`. Since the left-token count $k \le 2$ can only be 0, 1, or 2, an exhaustive case analysis on $k$ dispatches each case immediately using the supplied layer hypotheses $h0$, $h1$, and $h2$.

  1. To obtain the required dominating set, it suffices to show that the explicit family dominates every 3-token configuration with at most two left-part tokens.

    Applying `three_token_k2n_assemble_layer_cover` with the size hypothesis (hcard) reduces the existence of the desired dominating set to showing that any vertex $z$ whose left-part token count $k$ satisfies $k \le 2$ is either in the candidate family or adjacent to a member of it.

    line 15

    uses three_token_k2n_assemble_layer_cover

      apply three_token_k2n_assemble_layer_cover n hn hcard
  2. Every 3-token configuration with at most two left-part tokens is dominated by the explicit candidate family.

    Given an arbitrary vertex $z$ whose left-part token count is $k$ with $k \le 2$, the only possible values for $k$ are 0, 1, and 2. Performing this case analysis (`interval_cases k`) yields three subgoals, which are directly discharged by the respective layer domination hypotheses $h0$, $h1$, and $h2$.

    lines 16–20

      intro k hk z hz
      interval_cases k
      · exact h0 z hz
      · exact h1 z hz
      · exact h2 z hz
three_token_k2n_assemble_layer_cover
If the explicit candidate family of 3-tokens on $K_{2, n}$ satisfies the cardinality bound and dominates every 3-token configuration with at most two left-part tokens, then there exists a dominating set of the 3-token graph on $K_{2, n}$ satisfying the cardinality bound $\binom{\lfloor n/2 \rfloor}{2} + \binom{n - \lfloor n/2 \rfloor}{2} + n - 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_three_layers (n : ℕ) (hn : 4 ≤ n)    (hcard : (three_token_k2n_explicit_family n hn).card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2)    (h0 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 0 →      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)    (h1 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 1 →      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)    (h2 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 2 →      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  apply three_token_k2n_assemble_layer_cover n hn hcard  intro k hk z hz  interval_cases k  · exact h0 z hz  · exact h1 z hz  · exact h2 z hz
See it in the graphDiscuss this resultChallenge it