AFTD Auto-Formalizing Theoretical Domains

op_1627_realizable_parameters_seven_five_three_two

theoremverifiedoriginal

There exists an edge-coloring ϕ : (⊤ : SimpleGraph (Fin 5)).edgeSet → Finset (Fin 7) assigning a 5-element subset of Fin 7 to each edge of the complete graph on Fin 5 such that for every vertex v : Fin 5, the multiset of incident edge labels incident_edge_multiset ϕ v is a feasible packing for parameters (7, 5, 3, 2).

Statement

theorem op_1627_realizable_parameters_seven_five_three_two :
    ∃ ϕ : (⊤ : SimpleGraph (Fin 5)).edgeSet → Finset (Fin 7),
      (∀ e, (ϕ e).card = 5) ∧
      ∀ v : Fin 5, is_feasible_packing 7 5 3 2 (incident_edge_multiset ϕ v)
Related work
arXiv:2611.15376 Sec. 7, after Question 7.2
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_feasible_packingA multiset M of s-subsets of Fin r is a feasible packing for parameters (r, s, t, h) if every member of M has cardinality s and every…
  • incident_edge_multisetGiven an edge-coloring ϕ of the complete graph on a finite type V assigning a finite subset of Fin r to each edge, incident_edge_multiset…

Read back from the Lean

There exists an assignment $\phi$ of a subset of $\mathrm{Fin}(7)$ to each edge of the complete graph on $\mathrm{Fin}(5)$ such that: 1. For every edge $e$, the subset $\phi(e)$ has cardinality 5; and 2. For every vertex $v \in \mathrm{Fin}(5)$, the multiset of subsets assigned to the edges incident to $v$ forms a feasible packing with parameters $(r=7, s=5, t=3, h=2)$, meaning: - every subset in this multiset has cardinality 5, and - for every subset $T \subseteq \mathrm{Fin}(7)$ of cardinality 3, at most 2 of the edges incident to $v$ have $\phi(e)$ containing $T$ (counted with multiplicity).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The existence of the required edge-coloring is established by providing an explicit assignment ϕ of 5-element subsets of Fin 7 to each edge of K_5. Because K_5 has only 10 edges and 5 vertices, and the condition of being a feasible packing for parameters (7, 5, 3, 2) is shown to be decidable, verification reduces to finite computation. Lean's decide tactic checks all edge cardinalities and vertex packing conditions by direct exhaustive evaluation.

  1. The feasible packing property is_feasible_packing r s t h M is decidable for all parameters and multisets.

    Unfolding is_feasible_packing expresses the condition as a conjunction of two bounded statements: every set in M has cardinality s, and every t-element subset of Fin r is contained in at most h sets of M. Since all domains are finite and the cardinality relations are decidable, typeclass resolution (infer_instance) automatically derives the Decidable instance.

    lines 3–4

      unfold is_feasible_packing
      infer_instance
  2. The vertex-pair coloring op_1627_realizable_parameters_seven_five_three_two_color_pair is symmetric under swapping its two vertex arguments.

    Simplifying with the definition of op_1627_realizable_parameters_seven_five_three_two_color_pair shows that the assigned color set is determined by pattern matching on the pair (min u v, max u v). Rewriting with min_comm and max_comm shows that swapping u and v yields the same pair and therefore the same 5-element color set.

    lines 23–24

    uses min_comm, max_comm

      dsimp [op_1627_realizable_parameters_seven_five_three_two_color_pair]
      rw [min_comm, max_comm]
  3. There exists a 5-element subset edge-coloring of K_5 using colors from Fin 7 such that the incident edge labels at each vertex form a feasible packing for parameters (7, 5, 3, 2). automation

    The proof provides op_1627_realizable_parameters_seven_five_three_two_phi (the well-defined edge coloring obtained by lifting the symmetric pair coloring to the edge set of K_5) as the existential witness. The remaining goals—verifying that every edge is assigned a set of size 5, and that the incident edge multiset at each of the 5 vertices is a feasible packing—are closed by computational evaluation via the decide tactic.

    line 36

          ∀ v : Fin 5, is_feasible_packing 7 5 3 2 (incident_edge_multiset ϕ v) := ⟨op_1627_realizable_parameters_seven_five_three_two_phi, by decide⟩
min_comm
The minimum operation is commutative: min a b = min b a for any two elements in a linear order.
max_comm
The maximum operation is commutative: max a b = max b a for any two elements in a linear order.

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

instance op_1627_realizable_parameters_seven_five_three_two_decidable_feasible_packing    (r s t h : ℕ) (M : Multiset (Finset (Fin r))) : Decidable (is_feasible_packing r s t h M) := by  unfold is_feasible_packing  infer_instancedef op_1627_realizable_parameters_seven_five_three_two_color_pair (u v : ℕ) : Finset (Fin 7) :=  match min u v, max u v with  | 0, 1 => {0, 2, 3, 5, 6}  | 0, 2 => {0, 1, 2, 5, 6}  | 0, 3 => {1, 3, 4, 5, 6}  | 0, 4 => {0, 1, 3, 4, 5}  | 1, 2 => {0, 1, 2, 3, 4}  | 1, 3 => {0, 1, 4, 5, 6}  | 1, 4 => {1, 2, 3, 5, 6}  | 2, 3 => {0, 2, 3, 4, 5}  | 2, 4 => {0, 1, 4, 5, 6}  | 3, 4 => {0, 2, 3, 4, 6}  | _, _ => {0, 1, 2, 3, 4}lemma op_1627_realizable_parameters_seven_five_three_two_color_pair_symm (u v : Fin 5) :    op_1627_realizable_parameters_seven_five_three_two_color_pair u.val v.val =    op_1627_realizable_parameters_seven_five_three_two_color_pair v.val u.val := by  dsimp [op_1627_realizable_parameters_seven_five_three_two_color_pair]  rw [min_comm, max_comm]def op_1627_realizable_parameters_seven_five_three_two_phi :    (⊤ : SimpleGraph (Fin 5)).edgeSet → Finset (Fin 7) :=  fun e => Sym2.lift    ⟨fun u v => op_1627_realizable_parameters_seven_five_three_two_color_pair u.val v.val,     op_1627_realizable_parameters_seven_five_three_two_color_pair_symm⟩ e.val/-- For parameters (r, s, t, h) = (7, 5, 3, 2) where n = 3 and D = 4, there exists a (7, 5)-set-coloring of K_5 such that at every vertex v, the multiset of incident edge labels is a feasible packing. -/theorem op_1627_realizable_parameters_seven_five_three_two :    ∃ ϕ : (⊤ : SimpleGraph (Fin 5)).edgeSet → Finset (Fin 7),      (∀ e, (ϕ e).card = 5) ∧      ∀ v : Fin 5, is_feasible_packing 7 5 3 2 (incident_edge_multiset ϕ v) := ⟨op_1627_realizable_parameters_seven_five_three_two_phi, by decide⟩
See it in the graphDiscuss this resultChallenge it