wild_closed_cut_defect_partition
For a normalized minimum proper coloring on n vertices, an arbitrary finite family of vertex cuts D_j, and a nonnegative integer r, if n times the sum of d_j! times binomial(floor(n/2),floor(d_j/2)) times (n-d_j)! is strictly less than (r+1)n!, there is a permutation for which at most r cut-color pairs are closed.
Statement
theorem wild_closed_cut_defect_partition {n : ℕ} {J : Type*} [Fintype J] (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) (D : J → Finset (Fin n)) (r : ℕ) (hmass : n * (∑ j : J, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) < (r+1) * n.factorial) : ∃ σ : Equiv.Perm (Fin n), ((Finset.univ : Finset (J × Fin n)).filter (fun ji => w279_closed c ji.2 ((D ji.1).image σ))).card ≤ r
- Source
- Order-independent first-moment helper for the constant-defect structural route in OP-306. Generalizes the accepted n=13 one-defect averaging lemma without asserting that the numerical hypothesis holds at all orders.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_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…
- 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⌋.
The proof, explained
The theorem is established by contradiction using a double-counting (probabilistic method) argument. Assuming no suitable permutation exists, every permutation of vertices creates at least r + 1 closed cut-color pairs, forcing the total sum over all n! permutations to be at least (r + 1) n!. Swapping the summation order and bounding each cut-color event via w3_closed_event_card yields an upper bound of n ∑_j |D_j|! choose(n/2, |D_j|/2) (n - |D_j|)!. Under the mass hypothesis hmass, this upper bound is strictly less than (r + 1) n!, an impossible strict self-inequality.
Assume for contradiction that every permutation σ has strictly more than r closed cut-color pairs, and let Bad(σ) denote this set of closed pairs.
We proceed by contradiction using by_contra!, assuming that for every permutation σ ∈ S_n, the number of pairs (j, i) ∈ J × Fin n where the cut σ(D_j) is closed under color i is at least r + 1. The set Bad(σ) is defined to collect these closed pairs.
classical by_contra! h let Bad (σ : Equiv.Perm (Fin n)) : Finset (J × Fin n) := Finset.univ.filter (fun ji => w279_closed c ji.2 ((D ji.1).image σ))
The total count of closed pairs summed over all n! permutations is at least (r + 1) n!.
Since every permutation σ satisfies |Bad(σ)| ≥ r + 1, summing over all σ ∈ S_n gives a sum of at least |S_n| · (r + 1) by Finset.card_nsmul_le_sum. We evaluate |S_n| = n! using Fintype.card_perm, Fintype.card_fin, and Finset.card_univ, and rewrite the natural multiplication using nsmul_eq_mul and mul_comm.
uses
Finset.card_nsmul_le_sum,nsmul_eq_mul,mul_comm,Finset.card_univ,Fintype.card_perm,Fintype.card_finhave hlo : (r+1) * Nat.factorial n ≤ ∑ σ : Equiv.Perm (Fin n), (Bad σ).card := by have hi := Finset.card_nsmul_le_sum (s := (Finset.univ : Finset (Equiv.Perm (Fin n)))) (f := fun σ => (Bad σ).card) (n := r+1) (fun σ _ => by exact h σ) rw [nsmul_eq_mul, mul_comm, Finset.card_univ, Fintype.card_perm, Fintype.card_fin] at hi exact_mod_cast hi
The sum of |Bad(σ)| over all permutations equals the double sum over cuts j ∈ J and colors i of the number of permutations where (j, i) is closed.
By converting the set sizes to sums of 1 over indicators with Finset.card_eq_sum_ones and Finset.sum_filter, we interchange the order of summation between σ and the pair (j, i) via Finset.sum_comm. Recombining indicators and splitting the product index (j, i) into separate sums over j ∈ J and i ∈ Fin n using Finset.univ_product_univ and Finset.sum_product yields the transposed double sum.
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Finset.sum_comm,Finset.univ_product_univ,Finset.sum_producthave heq : (∑ σ : Equiv.Perm (Fin n), (Bad σ).card) = ∑ j : J, ∑ i : Fin n, (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i ((D 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 transposed sum is bounded above by ∑_{j ∈ J} ∑_{i ∈ Fin n} |D_j|! * choose(n/2, |D_j|/2) * (n - |D_j|)!.
For each fixed cut D_j and color i, the lemma w3_closed_event_card bounds the number of permutations σ making σ(D_j) closed under color i by |D_j|! * choose(n/2, |D_j|/2) * (n - |D_j|)!. Summing these termwise bounds across all j and i via Finset.sum_le_sum yields the upper bound.
uses
Finset.sum_le_sum,w3_closed_event_cardhave hup : (∑ j : J, ∑ i : Fin n, (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i ((D j).image σ))).card) ≤ ∑ j : J, ∑ _i : Fin n, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial := by exact Finset.sum_le_sum (fun j _ => Finset.sum_le_sum (fun i _ => w3_closed_event_card c m hm (D j) i))
The upper bound simplifies to n * ∑_{j ∈ J} |D_j|! * choose(n/2, |D_j|/2) * (n - |D_j|)!.
Because the summand does not depend on the color index i, the inner sum over all n elements of Fin n simply multiplies each term by n, using Finset.sum_const, Finset.card_univ, and Fintype.card_fin. Factoring n out of the outer sum with Finset.mul_sum gives the simplified expression.
uses
Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul,Finset.mul_sumhave heval : (∑ j : J, ∑ _i : Fin n, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) = n * (∑ j : J, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) := by simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] rw [← Finset.mul_sum] rfl
The lower and upper bounds contradict the mass hypothesis hmass.
Chaining the lower bound (r + 1) n! ≤ ∑_σ |Bad(σ)|, the equality transposition, the upper bound, and its simplification shows that (r + 1) n! ≤ n * ∑_{j ∈ J} ..., which directly contradicts the hypothesis hmass asserting that this latter quantity is strictly less than (r + 1) n!. The linear arithmetic tactic omega closes the contradiction.
omega
Finset.card_nsmul_le_sum- If each term in a finite sum over s is at least c, then |s| · c is at most the sum.
nsmul_eq_mul- Scalar multiplication by a natural number n coincides with multiplication by n in the semiring.
mul_comm- Multiplication is commutative: a * b = b * a.
Finset.card_univ- The cardinality of Finset.univ for a finite type is the cardinality of that type.
Fintype.card_perm- The number of permutations of a finite type of size k is k!.
Fintype.card_fin- The finite set Fin n has cardinality n.
Finset.card_eq_sum_ones- The cardinality of a finite set equals the sum of 1 over all its elements.
Finset.sum_filter- Summing over a filtered set {x ∈ s | p x} equals summing over s with an indicator if p x then f x else 0.
Finset.sum_comm- The order of two independent finite sums can be swapped: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
Finset.univ_product_univ- The Cartesian product of universal finsets is the universal finset of the product type.
Finset.sum_product- A sum over a Cartesian product set equals the nested iterated sum over the two components.
Finset.sum_le_sum- If f x ≤ g x for all elements x in a finite set, then the sum of f is at most the sum of g.
w3_closed_event_card- For a normalized coloring, a cut D, and a color i, the number of permutations σ making σ(D) closed for color i is at most |D|! * choose(n/2, |D|/2) * (n - |D|)!.
Finset.sum_const- The sum of a constant b over a finite set s equals |s| • b.
Finset.mul_sum- Multiplication distributes over a finite sum: a * ∑ i, f i = ∑ i, a * f i.
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 Classicalset_option maxHeartbeats 1000000theorem wild_closed_cut_defect_partition {n : ℕ} {J : Type*} [Fintype J] (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) (D : J → Finset (Fin n)) (r : ℕ) (hmass : n * (∑ j : J, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) < (r+1) * n.factorial) : ∃ σ : Equiv.Perm (Fin n), ((Finset.univ : Finset (J × Fin n)).filter (fun ji => w279_closed c ji.2 ((D ji.1).image σ))).card ≤ r := by classical by_contra! h let Bad (σ : Equiv.Perm (Fin n)) : Finset (J × Fin n) := Finset.univ.filter (fun ji => w279_closed c ji.2 ((D ji.1).image σ)) have hlo : (r+1) * Nat.factorial n ≤ ∑ σ : Equiv.Perm (Fin n), (Bad σ).card := by have hi := Finset.card_nsmul_le_sum (s := (Finset.univ : Finset (Equiv.Perm (Fin n)))) (f := fun σ => (Bad σ).card) (n := r+1) (fun σ _ => by exact h σ) rw [nsmul_eq_mul, mul_comm, Finset.card_univ, Fintype.card_perm, Fintype.card_fin] at hi exact_mod_cast hi have heq : (∑ σ : Equiv.Perm (Fin n), (Bad σ).card) = ∑ j : J, ∑ i : Fin n, (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i ((D 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 hup : (∑ j : J, ∑ i : Fin n, (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i ((D j).image σ))).card) ≤ ∑ j : J, ∑ _i : Fin n, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial := by exact Finset.sum_le_sum (fun j _ => Finset.sum_le_sum (fun i _ => w3_closed_event_card c m hm (D j) i)) have heval : (∑ j : J, ∑ _i : Fin n, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) = n * (∑ j : J, (D j).card.factorial * Nat.choose (n/2) ((D j).card/2) * (n-(D j).card).factorial) := by simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] rw [← Finset.mul_sum] rfl omega