three_token_k2n_assemble_layer_cover
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
- three_token_k2n_assemble_three_layersIf the explicit candidate family has the claimed cardinality and dominates each of the layers with zero, one and two left-part tokens, the…
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`.
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.
refine ⟨three_token_k2n_explicit_family n hn, ?_, hcard⟩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.
uses
three_token_k2n_left_count_le_twointro 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
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 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