op_1627_realizable_parameters_seven_five_three_two
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.
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.
unfold is_feasible_packing infer_instance
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.
uses
min_comm,max_commdsimp [op_1627_realizable_parameters_seven_five_three_two_color_pair] rw [min_comm, max_comm]
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.
∀ 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.
- The core verification that the explicit edge-coloring satisfies the (7, 5, 3, 2)-feasible packing condition at every vertex is carried out entirely by the decide tactic via computational evaluation over finite sets, rather than an analytical paper proof.
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.
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⟩