wild_complete_thirteen_one_defect_partition
For every normalized minimum proper coloring of K_13, there exists a vertex permutation of the block partition 3+3+3+4 for which at most one pair consisting of one of the seven cuts up to complementation and a color is closed. The hypothesis gives a bijection m between colors and their unique missing vertices; E is exactly the set of closed cut-color pairs after the permutation.
Statement
theorem wild_complete_thirteen_one_defect_partition
(c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13)) (m : Fin 13 ≃ Fin 13)
(hm : ∀ (i v : Fin 13), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) :
∃ (σ : Equiv.Perm (Fin 13)) (E : Finset (Fin 7 × Fin 13)), E.card ≤ 1 ∧
∀ ji : Fin 7 × Fin 13, ji ∈ E ↔
w279_closed c ji.2 ((wsc_repair_cuts wsc_repair_blocks ji.1).image σ)- Source
- First-moment helper for the finite n=13 case of OP-306. The seven cut sizes are 3,3,3,4,6,6,6. The total expected number of closed cut-color pairs is bounded by 17/11<2. This does not itself produce a seal-free partition, and the one-swap repair obstruction shows the missing step is substantive.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- wild_complete_thirteen_one_swap_repair_obstructionThere exists a minimum proper 13-coloring of K_13, normalized so that color i misses vertex i, with this property. The fixed partition…
- wild_number_complete_graph_upper_sub_four_add_parityFor every integer n>=13, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge coloring c…
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
The proof, explained
The proof uses the probabilistic method / double counting by contradiction. If every permutation σ had at least two closed cut-color pairs, the total number of incidences over all 13! permutations would be at least 2 * 13!. However, exchanging the summation order and bounding the number of permutations closing any cut-color pair yields an upper bound of 13 * ∑_{j=0}^6 bound(j), which is strictly less than 2 * 13! by direct computation, yielding a contradiction.
The sum of the cut bounds over all 7 cuts, scaled by 13, is strictly less than 2 * 13! automation
This finite numerical inequality is verified by direct calculation using the decide tactic.
decideAssume for contradiction that no valid permutation σ exists, define Bad(σ) as the set of closed cut-color pairs for σ, and deduce that |Bad(σ)| ≥ 2 for all σ
We proceed by contradiction: if the theorem were false, then for every permutation σ and any set E with |E| ≤ 1, E cannot equal the set of closed pairs. In particular, choosing E = Bad(σ) (the actual set of closed pairs for σ), we must have |Bad(σ)| ≥ 2, since otherwise Bad(σ) itself would be a valid witness E of size at most 1.
uses
Finset.mem_filter,Finset.mem_univ,true_andclassical by_contra! h let Bad (σ : Equiv.Perm (Fin 13)) : Finset (Fin 7 × Fin 13) := Finset.univ.filter (fun ji => w279_closed c ji.2 ((wsc_repair_cuts wsc_repair_blocks ji.1).image σ)) have h2 : ∀ σ, 2 ≤ (Bad σ).card := by intro σ have hσ := h σ (Bad σ) by_contra! hlt obtain ⟨ji, ⟨h1, h2⟩ | ⟨h1, h2⟩⟩ := hσ (by omega) · simp only [Bad, Finset.mem_filter, Finset.mem_univ, true_and] at h1 exact h2 h1 · simp only [Bad, Finset.mem_filter, Finset.mem_univ, true_and] at h1 exact h1 h2
The sum of |Bad(σ)| over all permutations σ is at least 2 * 13!
Since each of the 13! permutations σ has |Bad(σ)| ≥ 2, summing over all σ ∈ S₁₃ gives at least 2 * 13!.
uses
Finset.card_nsmul_le_sum,nsmul_eq_mul,mul_comm,Finset.card_univ,Fintype.card_perm,Fintype.card_finhave h_sum_lower : 2 * Nat.factorial 13 ≤ ∑ σ : Equiv.Perm (Fin 13), (Bad σ).card := by have h_le := Finset.card_nsmul_le_sum (s := (Finset.univ : Finset (Equiv.Perm (Fin 13)))) (f := fun σ => (Bad σ).card) (n := 2) (fun σ _ => h2 σ) rw [nsmul_eq_mul, mul_comm, Finset.card_univ, Fintype.card_perm, Fintype.card_fin] at h_le exact h_le
Exchanging the order of summation expresses the total badness as the sum over cuts and colors of the number of permutations closing each cut-color pair
By double counting (rewriting the sizes of Bad(σ) as sums of indicator variables and commuting the summations), the sum of |Bad(σ)| over σ equals the sum over cuts j ∈ Fin 7 and colors i ∈ Fin 13 of the number of permutations σ that make cut j closed for color i.
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Finset.sum_comm,Finset.univ_product_univ,Finset.sum_producthave h_sum_eq : (∑ σ : Equiv.Perm (Fin 13), (Bad σ).card) = ∑ j : Fin 7, ∑ i : Fin 13, (Finset.univ.filter (fun σ : Equiv.Perm (Fin 13) => w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ))).card := by simp_rw [Bad, Finset.card_eq_sum_ones, Finset.sum_filter] rw [Finset.sum_comm] simp_rw [← Finset.sum_filter, ← Finset.card_eq_sum_ones] rw [← Finset.univ_product_univ, Finset.sum_product]
The number of permutations closing each cut-color pair is upper bounded by the cut bound
Applying the lemma w3_closed_event_card to each cut j and color i shows that the number of permutations closing cut j for color i is at most wild_complete_thirteen_one_defect_partition_cut_bound j.
uses
Finset.sum_le_sum,w3_closed_event_cardhave h_sum_upper : (∑ j : Fin 7, ∑ i : Fin 13, (Finset.univ.filter (fun σ : Equiv.Perm (Fin 13) => w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ))).card) ≤ ∑ j : Fin 7, ∑ i : Fin 13, wild_complete_thirteen_one_defect_partition_cut_bound j := by apply Finset.sum_le_sum intro j _ apply Finset.sum_le_sum intro i _ exact w3_closed_event_card c m hm (wsc_repair_cuts wsc_repair_blocks j) i
Summing over all 13 colors simplifies the upper bound to 13 times the sum over the 7 cuts
Since the cut bound depends only on the cut j and not on the color i, summing over the 13 colors multiplies the bound for cut j by 13, and factoring out 13 yields 13 * ∑_j bound(j).
uses
Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul,Finset.mul_sumhave h_sum_eval : (∑ j : Fin 7, ∑ _i : Fin 13, wild_complete_thirteen_one_defect_partition_cut_bound j) = 13 * ∑ j : Fin 7, wild_complete_thirteen_one_defect_partition_cut_bound j := by simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] rw [← Finset.mul_sum] rfl
The lower bound 2 * 13! and upper bound strictly less than 2 * 13! contradict each other automation
The lower bound gives ∑ |Bad(σ)| ≥ 2 * 13!, while the upper bound gives ∑ |Bad(σ)| ≤ 13 * ∑_j bound(j), which by wild_complete_thirteen_one_defect_partition_sum_bound is strictly less than 2 * 13!, a contradiction.
uses
wild_complete_thirteen_one_defect_partition_sum_boundhave h_lt := wild_complete_thirteen_one_defect_partition_sum_bound omega
Finset.mem_filter- characterization of membership in a filtered finset
Finset.mem_univ- every element of a finite type is in the universal finset
true_and- a conjunction of True and p simplifies to p
Finset.card_nsmul_le_sum- multiplying the cardinality of a finite set by a lower bound on its elements bounds the sum from below
nsmul_eq_mul- scalar multiplication of a natural number with an element equals the product
mul_comm- multiplication is commutative
Finset.card_univ- the cardinality of the universal finset is the cardinality of the underlying fintype
Fintype.card_perm- the number of permutations of a finite type of size n is n!
Fintype.card_fin- the cardinality of Fin n is n
Finset.card_eq_sum_ones- the cardinality of a finset is the sum of ones over its elements
Finset.sum_filter- sum of a function over a filtered finset equals the sum of an if-then-else over the original finset
Finset.sum_comm- the order of two finite summations can be exchanged
Finset.univ_product_univ- the Cartesian product of two universal finsets is the universal finset on pairs
Finset.sum_product- a sum over a Cartesian product finset equals an iterated sum over the factor finsets
Finset.sum_le_sum- termwise inequality implies inequality of finite sums
w3_closed_event_card- upper bound on the number of permutations closing a cut for a given color
Finset.sum_const- sum of a constant over a finset equals the cardinality times the constant
Finset.mul_sum- factoring a constant out of a finite sum
wild_complete_thirteen_one_defect_partition_sum_bound- the arithmetic inequality bounding 13 times the sum of the 7 cut bounds strictly below 2 * 13!
- The auxiliary lemma wild_complete_thirteen_one_defect_partition_sum_bound is verified entirely by Lean's computational kernel (the decide tactic) by evaluating the finite sum of factorials and binomial coefficients.
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.
open scoped BigOperators Classicalprivate def wild_complete_thirteen_one_defect_partition_cut_bound (j : Fin 7) : ℕ := (wsc_repair_cuts wsc_repair_blocks j).card.factorial * (13 / 2).choose ((wsc_repair_cuts wsc_repair_blocks j).card / 2) * (13 - (wsc_repair_cuts wsc_repair_blocks j).card).factorialprivate lemma wild_complete_thirteen_one_defect_partition_sum_bound : 13 * (∑ j : Fin 7, wild_complete_thirteen_one_defect_partition_cut_bound j) < 2 * Nat.factorial 13 := by decidetheorem wild_complete_thirteen_one_defect_partition (c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13)) (m : Fin 13 ≃ Fin 13) (hm : ∀ (i v : Fin 13), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) : ∃ (σ : Equiv.Perm (Fin 13)) (E : Finset (Fin 7 × Fin 13)), E.card ≤ 1 ∧ ∀ ji : Fin 7 × Fin 13, ji ∈ E ↔ w279_closed c ji.2 ((wsc_repair_cuts wsc_repair_blocks ji.1).image σ) := by classical by_contra! h let Bad (σ : Equiv.Perm (Fin 13)) : Finset (Fin 7 × Fin 13) := Finset.univ.filter (fun ji => w279_closed c ji.2 ((wsc_repair_cuts wsc_repair_blocks ji.1).image σ)) have h2 : ∀ σ, 2 ≤ (Bad σ).card := by intro σ have hσ := h σ (Bad σ) by_contra! hlt obtain ⟨ji, ⟨h1, h2⟩ | ⟨h1, h2⟩⟩ := hσ (by omega) · simp only [Bad, Finset.mem_filter, Finset.mem_univ, true_and] at h1 exact h2 h1 · simp only [Bad, Finset.mem_filter, Finset.mem_univ, true_and] at h1 exact h1 h2 have h_sum_lower : 2 * Nat.factorial 13 ≤ ∑ σ : Equiv.Perm (Fin 13), (Bad σ).card := by have h_le := Finset.card_nsmul_le_sum (s := (Finset.univ : Finset (Equiv.Perm (Fin 13)))) (f := fun σ => (Bad σ).card) (n := 2) (fun σ _ => h2 σ) rw [nsmul_eq_mul, mul_comm, Finset.card_univ, Fintype.card_perm, Fintype.card_fin] at h_le exact h_le have h_sum_eq : (∑ σ : Equiv.Perm (Fin 13), (Bad σ).card) = ∑ j : Fin 7, ∑ i : Fin 13, (Finset.univ.filter (fun σ : Equiv.Perm (Fin 13) => w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ))).card := by simp_rw [Bad, Finset.card_eq_sum_ones, Finset.sum_filter] rw [Finset.sum_comm] simp_rw [← Finset.sum_filter, ← Finset.card_eq_sum_ones] rw [← Finset.univ_product_univ, Finset.sum_product] have h_sum_upper : (∑ j : Fin 7, ∑ i : Fin 13, (Finset.univ.filter (fun σ : Equiv.Perm (Fin 13) => w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ))).card) ≤ ∑ j : Fin 7, ∑ i : Fin 13, wild_complete_thirteen_one_defect_partition_cut_bound j := by apply Finset.sum_le_sum intro j _ apply Finset.sum_le_sum intro i _ exact w3_closed_event_card c m hm (wsc_repair_cuts wsc_repair_blocks j) i have h_sum_eval : (∑ j : Fin 7, ∑ _i : Fin 13, wild_complete_thirteen_one_defect_partition_cut_bound j) = 13 * ∑ j : Fin 7, wild_complete_thirteen_one_defect_partition_cut_bound j := by simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] rw [← Finset.mul_sum] rfl have h_lt := wild_complete_thirteen_one_defect_partition_sum_bound omega