wild_number_complete_graph_upper_sub_four_add_parity
For 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 of K_n with color set Fin k, the wild number is at most (n-4)+(n mod 2). This is n-3 for odd n>=13 and n-4 for even n>=14.
Statement
theorem wild_number_complete_graph_upper_sub_four_add_parity (n k : ℕ) (hn : 13 ≤ n)
(hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k)
(c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) :
simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c ≤ n-4+n%2- Related work
- arXiv:2610.22142, Section 3.3.4, Theorem 3.6 and its even-order corollary give n-2 for odd n and n-3 for even n. This strengthens each weak upper bound by one on n>=13. The proof randomly permutes two triples and the remaining n-6 vertices; closure of the remaining block is equivalent to closure of the union of the triples. No equality with the conjectured lower bound is asserted.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- wild_number_complete_graph_large_eqFor every integer n>=30000001, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge…
- 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…
- permutation_partial_assignment_card_bound_of_switchingIf a finite set of permutations is closed under undoing any one forced assignment by an image swap, its number extending an injective…
- simple_graph_wild_number_le_of_block_cut_conditionLet a nonempty complete graph have a vertex-to-block map p and one root r(i) in each of q blocks. If every used color has an edge crossing…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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⌋.
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod.
- Used by 3
- wild_complete_thirteen_one_defect_partitionFor 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…
- wild_number_complete_thirteen_fourteen_eq_nine_or_tenFor n=13 or n=14, every minimum proper edge coloring of K_n has wild number either 9 or 10.
- wild_closed_cut_defect_partitionFor a normalized minimum proper coloring on n vertices, an arbitrary finite family of vertex cuts D_j, and a nonnegative integer r, if n…
Read back from the Lean
For any natural numbers $n$ and $k$, assuming: 1. $13 \le n$, 2. $k$ is the chromatic number of the line graph of the complete graph $K_n$ on vertex set $\mathrm{Fin}(n)$ (i.e., $k$ is the chromatic index $\chi'(K_n)$), and 3. $c$ is a proper coloring of the line graph of $K_n$ with colors in $\mathrm{Fin}(k)$ (i.e., a proper edge-coloring of $K_n$ using $k$ colors), the "wild number" of $K_n$ with respect to $c$ (the minimum size of an edge set $W \subseteq E(K_n)$ such that for every edge $e$, adding $W$ to the edges of color $c(e)$ produces a connected spanning subgraph) is at most $(n - 4) + (n \bmod 2)$ (which equals $n - 4$ if $n$ is even, and $n - 3$ if $n$ is odd).
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 theorem bounds the wild number of the complete graph K_n under an optimal edge coloring by (n - 4) + (n mod 2) for all n ≥ 13. For odd n, the vertices are partitioned into three blocks (two of size 3 and one of size n - 6) using the probabilistic method: counting arguments and polynomial bounds ensure there exists a permutation whose block images are never closed under any color matching, so every color crosses every non-trivial cut, yielding wild number ≤ n - 3. For even n, the coloring is restricted to the odd subgraph K_{n-1}, where the 3-partition is constructed and then lifted to K_n to achieve the bound ≤ n - 4.
The number of permutations of Fin n extending a given injective partial map f on D is at most (n - |D|)!.
We apply the switching bound lemma permutation_partial_assignment_card_bound_of_switching to the universe of permutations, which bounds n^{\underline{|D|}} times the fiber by n!. Dividing both sides by n^{\underline{|D|}} via Nat.le_of_mul_le_mul_left yields the bound (n - |D|)!.
uses
permutation_partial_assignment_card_bound_of_switching,Nat.factorial_mul_descFactorial,Nat.descFactorial_pos,Nat.le_of_mul_le_mul_left,Nat.mul_comm,Finset.card_le_univclassical have hi := permutation_partial_assignment_card_bound_of_switching D f hf (Finset.univ : Finset (Equiv.Perm (Fin n))) (by intro a ha σ hσ hσa y; exact Finset.mem_univ _) simp only [Fintype.card_fin, Finset.card_univ, Fintype.card_perm] at hi have hd : D.card ≤ n := by simpa using Finset.card_le_univ D have he := Nat.factorial_mul_descFactorial hd have hp : 0 < (n : ℕ).descFactorial D.card := Nat.descFactorial_pos.2 hd apply Nat.le_of_mul_le_mul_left (c := (n : ℕ).descFactorial D.card) (hc := hp) convert hi.trans_eq (he.symm.trans (Nat.mul_comm _ _)) using 1 congr 1 apply congrArg Finset.card ext σ simp only [Finset.mem_filter, Finset.mem_univ, true_and]
Every permutation σ whose image σ(D) is closed under color i projects to an injection φ(σ) agreeing with σ on D and the identity elsewhere.
We define φ(σ)(x) to be σ(x) if x ∈ D and x otherwise. Since σ is injective, φ(σ) is injective on D and satisfies φ(σ)(D) = σ(D), so φ(σ)(D) is also closed under color i.
uses
if_neg,if_pos,Finset.image_congrclassical let A : Finset (Equiv.Perm (Fin n)) := Finset.univ.filter fun σ => w279_closed c i (D.image σ) let F : Finset (Fin n → Fin n) := Finset.univ.filter fun f => (∀ x ∉ D, f x = x) ∧ Set.InjOn f (↑D : Set (Fin n)) ∧ w279_closed c i (D.image f) let φ : Equiv.Perm (Fin n) → Fin n → Fin n := fun σ x => if x ∈ D then σ x else x have hmaps : ∀ σ ∈ A, φ σ ∈ F := by intro σ hσ simp only [F, Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨?_, ?_, ?_⟩ · intro x hx; simp only [φ, if_neg hx] · intro x hx y hy he change x ∈ D at hx change y ∈ D at hy dsimp only [φ] at he rw [if_pos hx, if_pos hy] at he exact σ.injective he · have he : D.image (φ σ) = D.image σ := by apply Finset.image_congr intro x hx change x ∈ D at hx simp only [φ, if_pos hx] rw [he] exact (Finset.mem_filter.1 hσ).2
The number of permutations mapping D to a set closed under color i is at most |D|! * \binom{n/2}{|D|/2} * (n - |D|)!.
The number of partial injections on D whose image is closed under color i is bounded by |D|! * \binom{n/2}{|D|/2} using w279_count_events and w279_count_closed (since color i forms a matching of size n/2). Decomposing the set of permutations fiberwise over φ, each fiber has size at most (n - |D|)! by w3_assignment_card. Summing over all fibers yields the product bound.
uses
w279_count_events,w279_count_closed,w279_card_R,Finset.card_eq_sum_card_fiberwise,smul_eq_mul,Finset.sum_const,Finset.sum_le_sum,w3_assignment_card,Nat.mul_le_mul_left,Nat.mul_le_mul_righthave hF : F.card ≤ D.card.factorial * Nat.choose (n/2) (D.card/2) := by have hi := w279_count_events D (fun U => w279_closed c i U) have hc := w279_count_closed c m hm i D.card have hr : (w279_R c m i).card = n/2 := by have := w279_card_R c m hm i; omega rw [hr] at hc exact hi.trans (Nat.mul_le_mul_left _ hc) have hb : A.card ≤ F.card * (n-D.card).factorial := by rw [Finset.card_eq_sum_card_fiberwise (f := φ) (t := F) hmaps] rw [← smul_eq_mul, ← Finset.sum_const] refine Finset.sum_le_sum fun f hf => ?_ have hfi := (Finset.mem_filter.1 hf).2.2.1 refine (Finset.card_le_card ?_).trans (w3_assignment_card D f hfi) intro σ hσ rw [Finset.mem_filter] at hσ ⊢ refine ⟨Finset.mem_univ _, ?_⟩ intro x hx have he := congrFun hσ.2 x simpa only [φ, if_pos hx] using he exact hb.trans (Nat.mul_le_mul_right _ hF)
For odd n ≥ 13, n * (12(n/2)(n-3)^{\underline 3} + 120(n/2)^3) < n^{\underline 6}. automation
Writing n = 2r + 13 for r ≥ 0, we express both sides as explicit polynomials in r and verify the strict inequality using non-linear arithmetic (nlinarith) together with positivity of the difference.
uses
Nat.descFactorial_succ,Nat.descFactorial_zero,Nat.sub_zero,Nat.sub_subobtain ⟨r,rfl⟩ : ∃ r : ℕ, n=2*r+13 := by exact ⟨(n-13)/2, by omega⟩ have hm : (2*r+13)/2 = r+6 := by omega rw [hm] norm_num only [Nat.descFactorial_succ, Nat.descFactorial_zero, Nat.sub_zero, Nat.sub_sub] simp only [show 2*r+13-1=2*r+12 by omega, show 2*r+13-2=2*r+11 by omega, show 2*r+13-3=2*r+10 by omega, show 2*r+13-4=2*r+9 by omega, show 2*r+13-5=2*r+8 by omega] have hp : 0 < (2*r+13)*2*(r+6)*(16*r^4+256*r^3+1448*r^2+3140*r+1440) := by positivity nlinarith only [hp]
For odd n ≥ 13, the total count of permutations making some cut closed is strictly less than n!.
We factor out (n - 6)! from the expression n * (2 * 3! * \binom{n/2}{1} * (n - 3)! + 6! * \binom{n/2}{3} * (n - 6)!). Using \binom{n/2}{3} * 6! = 120 * (n/2)^{\underline 3} ≤ 120 * (n/2)^3, we bound the sum by (n - 6)! times the polynomial from w3_mass_polynomial, which is strictly less than (n - 6)! * n^{\underline 6} = n!.
uses
Nat.descFactorial_le_pow,Nat.descFactorial_eq_factorial_mul_choose,Nat.factorial_mul_descFactorial,w3_mass_polynomial,Nat.choose_one_right,Nat.mul_le_mul_left,Nat.mul_lt_mul_of_pos_left,Nat.factorial_poshave hc := Nat.descFactorial_le_pow (n/2) 3 rw [Nat.descFactorial_eq_factorial_mul_choose] at hc norm_num only [Nat.factorial_succ, Nat.factorial_zero] at hc have h1 := Nat.factorial_mul_descFactorial (n := n) (k := 6) (by omega : 6 ≤ n) have h2 := Nat.factorial_mul_descFactorial (n := n-3) (k := 3) (by omega : 3 ≤ n-3) simp only [Nat.sub_sub, show 3+3=6 by decide] at h2 have hp := w3_mass_polynomial n hn hodd calc _ ≤ (n-6).factorial * (n*(12*(n/2)*(n-3).descFactorial 3+120*(n/2)^3)) := by rw [← h2] norm_num only [Nat.factorial_succ, Nat.factorial_zero, Nat.choose_one_right] have hi := Nat.mul_le_mul_left (120*n*(n-6).factorial) hc nlinarith only [hi] _ < (n-6).factorial * n.descFactorial 6 := Nat.mul_lt_mul_of_pos_left hp (Nat.factorial_pos _) _ = _ := h1
The block position sets have sizes |positions(0)| = 3, |positions(1)| = 3, and |positions(2)| = 6.
We partition the first six vertices into blocks of size 3 and the remaining vertices into block 2. For each selector j, the positions set is explicitly identified by extensionality, and its cardinality is verified by counting elements.
uses
w3_sel,w3_positions,w3_block,Fin.ext_iffinstance w3_sel_decidable (j b : Fin 3) : Decidable (w3_sel j b) := by unfold w3_sel; infer_instance def w3_positions (j : Fin 3) : Finset (Fin n) := Finset.univ.filter fun v => w3_sel j (w3_block v) lemma w3_mem_positions (j : Fin 3) (v : Fin n) : v ∈ w3_positions j ↔ w3_sel j (w3_block v) := by simp [w3_positions] lemma w3_positions_card (hn : 7 ≤ n) (j : Fin 3) : (w3_positions (n := n) j).card = if j=2 then 6 else 3 := by have he0 : w3_positions (n := n) 0 = {⟨0,by omega⟩,⟨1,by omega⟩,⟨2,by omega⟩} := by ext v simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block, Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] split_ifs <;> omega have he1 : w3_positions (n := n) 1 = {⟨3,by omega⟩,⟨4,by omega⟩,⟨5,by omega⟩} := by ext v simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block, Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] split_ifs <;> omega have he2 : w3_positions (n := n) 2 = {⟨0,by omega⟩,⟨1,by omega⟩,⟨2,by omega⟩,⟨3,by omega⟩,⟨4,by omega⟩,⟨5,by omega⟩} := by ext v simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block, Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] split_ifs <;> omega fin_cases j <;> norm_num [he0, he1, he2, Fin.ext_iff] change (w3_positions (n := n) 2).card = 6 rw [he2] norm_num [Fin.ext_iff]
The canonical roots satisfy w3_block(3j) = j, and every non-trivial cut in Fin 3 is selected by w3_sel j or its complement. automation
Direct calculation confirms that vertex 3j belongs to block j. For the cut classification w3_cut_shape, the kernel decision procedure (decide +kernel) exhaustively checks all non-empty proper subsets of Fin 3.
uses
w3_block,Fin.ext_ifflemma w3_root (hn : 7 ≤ n) (j : Fin 3) : w3_block (⟨3*j.val, by have := j.isLt; omega⟩ : Fin n) = j := by fin_cases j <;> norm_num [w3_block, Fin.ext_iff] lemma w3_cut_shape : ∀ S : Finset (Fin 3), S.Nonempty → S ≠ Finset.univ → ∃ j : Fin 3, (∀ b : Fin 3, b ∈ S ↔ w3_sel j b) ∨ (∀ b : Fin 3, b ∈ S ↔ ¬w3_sel j b) := by decide +kernel
There exists a permutation σ such that no block position set is closed under any color.
By the union bound, the number of permutations making some block position set closed under some color is at most the sum over all (j, i) of w3_closed_event_card. Substituting the cardinalities 3, 3, and 6, this sum is bounded by w3_mass_lt, which is strictly less than |S_n| = n!. Hence the bad permutations do not cover S_n, and a good permutation σ exists.
uses
Finset.card_biUnion_le,w3_closed_event_card,Fintype.sum_prod_type,w3_positions_card,Fin.sum_univ_succ,Finset.card_univ,Fintype.card_perm,Fintype.card_fin,w3_mass_lt,lt_irrefl,Finset.eq_univ_of_forall,Finset.mem_biUnionclassical let Bad : Fin 3 × Fin n → Finset (Equiv.Perm (Fin n)) := fun ji => Finset.univ.filter fun σ => w279_closed c ji.2 ((w3_positions (n := n) ji.1).image σ) let B : Finset (Equiv.Perm (Fin n)) := Finset.univ.biUnion Bad have hb : B.card ≤ n*(2*(3 : ℕ).factorial*Nat.choose (n/2) 1*(n-3).factorial+ (6 : ℕ).factorial*Nat.choose (n/2) 3*(n-6).factorial) := by refine Finset.card_biUnion_le.trans ?_ have hi : ∑ ji : Fin 3 × Fin n, (Bad ji).card ≤ ∑ ji : Fin 3 × Fin n, (w3_positions (n := n) ji.1).card.factorial * Nat.choose (n/2) ((w3_positions (n := n) ji.1).card/2) * (n-(w3_positions (n := n) ji.1).card).factorial := by exact Finset.sum_le_sum fun ji hji => w3_closed_event_card c m hm (w3_positions (n := n) ji.1) ji.2 refine hi.trans_eq ?_ rw [Fintype.sum_prod_type] simp only [w3_positions_card (by omega : 7 ≤ n)] norm_num [Fin.sum_univ_succ, Fin.ext_iff] ring have hlt : B.card < (Finset.univ : Finset (Equiv.Perm (Fin n))).card := by rw [Finset.card_univ, Fintype.card_perm, Fintype.card_fin] exact hb.trans_lt (w3_mass_lt n hn hodd) have hne : B ≠ Finset.univ := by intro he; rw [he] at hlt; exact lt_irrefl _ hlt have hex : ∃ σ : Equiv.Perm (Fin n), σ ∉ B := by by_contra h push Not at h exact hne (Finset.eq_univ_of_forall h) obtain ⟨σ,hσ⟩ := hex refine ⟨σ, ?_⟩ intro j i hi exact hσ (Finset.mem_biUnion.2 ⟨(j,i), Finset.mem_univ _, Finset.mem_filter.2 ⟨Finset.mem_univ _,hi⟩⟩)
For odd n ≥ 13, there exists a 3-partition p with roots such that every color crosses every non-trivial cut.
Using the good permutation σ from w3_avoid_blocks, we define p(v) = w3_block(σ^{-1}(v)) and roots(j) = σ(3j). If some color c(e) had no edge crossing cut S, the preimage under p would be closed under c(e). By w3_cut_shape, this preimage corresponds to σ(positions(j)) or its complement, which contradicts the choice of σ.
uses
w3_avoid_blocks,Equiv.symm_apply_apply,w3_root,w3_cut_shape,Finset.mem_image,w3_mem_positions,Ne.symm,w279_c_swapclassical obtain ⟨σ,hσ⟩ := w3_avoid_blocks hn hodd c m hm refine ⟨(fun v => w3_block (σ.symm v)), (fun j => σ ⟨3*j.val, by have := j.isLt; omega⟩), ?_, ?_⟩ · intro j simpa only [Equiv.symm_apply_apply] using w3_root (by omega : 7 ≤ n) j · intro e S hS hSu by_contra hno push Not at hno obtain ⟨j,hj | hj⟩ := w3_cut_shape S hS hSu · apply hσ j (c e) intro u hu v huv hc obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu have hxu := (w3_mem_positions j x).1 hx by_contra hv have hxS := (hj _).2 hxu have hvS : w3_block (σ.symm v) ∉ S := by intro hvS apply hv exact Finset.mem_image.2 ⟨σ.symm v, (w3_mem_positions _ _).2 ((hj _).1 hvS), by simp⟩ exact hno (σ x) v huv (by simpa using hxS) hvS hc · apply hσ j (c e) intro u hu v huv hc obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu have hxu := (w3_mem_positions j x).1 hx by_contra hv have hxS : w3_block (σ.symm (σ x)) ∉ S := by intro hh exact (hj _).1 (by simpa using hh) hxu have hvS : w3_block (σ.symm v) ∈ S := by apply (hj _).2 intro hvj exact hv (Finset.mem_image.2 ⟨σ.symm v, (w3_mem_positions _ _).2 hvj, by simp⟩) exact hno v (σ x) (Ne.symm huv) hvS hxS ((w279_c_swap c huv).symm.trans hc)
When n is odd and n ≥ 13, the wild number of K_n is at most n - 3 = (n - 4) + (n mod 2).
For odd n, the chromatic index is k = n, and each color misses a unique vertex, yielding a bijection m. Applying w3_partition provides a 3-partition with roots where every color crosses every cut. By simple_graph_wild_number_le_of_block_cut_condition with q = 3, the wild number is at most n - 3.
uses
w279_missing_vertex_equiv,Fintype.card_congr,w3_partition,simple_graph_wild_number_le_of_block_cut_conditionby_cases hodd : n%2=1 · obtain ⟨m,hm⟩ := w279_missing_vertex_equiv n k (by omega) hodd hk c have hk' : k=n := by simpa using Fintype.card_congr m subst k obtain ⟨p,roots,hr,hc⟩ := w3_partition hn hodd c m hm have hu := simple_graph_wild_number_le_of_block_cut_condition (n := n) (q := 3) (by omega) c p roots hr hc omega
When n is even and n ≥ 14, the wild number of K_n is at most n - 4 = (n - 4) + (n mod 2).
When n is even, m = n - 1 ≥ 13 is odd, and the chromatic index is k = m. Restricting the coloring to K_m gives an m-coloring cc of K_m. Applying w3_partition on K_m yields a 3-partition crossing all cuts for all colors. We then lift this partition to K_n via wsc_even_upper_of_partition to conclude that the wild number of K_n is at most (m + 1) - 4 - 1 = n - 4.
uses
Nat.exists_eq_succ_of_ne_zero,wsc_even_min_colors,wsc_restrict_color,wsc_missing_vertex_equiv_of_le,w3_partition,wsc_color_used,wsc_even_upper_of_partition· obtain ⟨m,rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0) have hm13 : 13 ≤ m := by omega have hmOdd : m%2=1 := by omega have hk' : k=m := wsc_even_min_colors (by omega) hmOdd hk c subst k let cc := wsc_restrict_color c obtain ⟨miss,hmiss⟩ := wsc_missing_vertex_equiv_of_le m m (by omega) hmOdd le_rfl cc obtain ⟨p,roots,hr,hcuts⟩ := w3_partition hm13 hmOdd cc miss hmiss have hc : ∀ (i : Fin m) (S : Finset (Fin 3)), S.Nonempty → S ≠ Finset.univ → ∃ (u v : Fin m) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ cc ⟨s(u,v),wild_kn_mem huv⟩ = i := by intro i S hS hSu obtain ⟨e,he⟩ := wsc_color_used (by omega) cc miss hmiss i obtain ⟨u,v,huv,hu,hv,hcol⟩ := hcuts e S hS hSu exact ⟨u,v,huv,hu,hv,hcol.trans he⟩ have hu := wsc_even_upper_of_partition (by omega) c p roots hr hc omega
permutation_partial_assignment_card_bound_of_switching- The number of permutations extending an injective map on a subset D multiplied by n^{\underline{|D|}} is at most the total number of permutations.
Nat.factorial_mul_descFactorial- For k ≤ n, (n - k)! * n^{\underline k} = n!.
Nat.descFactorial_pos- The falling factorial n^{\underline k} is strictly positive if and only if k ≤ n.
Nat.le_of_mul_le_mul_left- If c * a ≤ c * b and c > 0, then a ≤ b.
Nat.mul_comm- Multiplication of natural numbers is commutative.
Finset.card_le_univ- The cardinality of any subset of a finite type is at most the cardinality of the type.
if_neg- If a boolean condition is false, the conditional expression reduces to the else branch.
if_pos- If a boolean condition is true, the conditional expression reduces to the then branch.
Finset.image_congr- If two functions agree pointwise on a set, their images of that set are equal.
w279_count_events- The number of partial injections on D whose image satisfies property P is at most |D|! times the number of subsets of size |D| satisfying P.
w279_count_closed- The number of subsets of size s closed under color i in a near-factored complete graph is at most \binom{|R_i|}{s/2}.
w279_card_R- The size of the color matching R_i satisfies n = 2|R_i| + 1, so |R_i| = n/2.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set is the sum of the cardinalities of its fibers under any mapping.
smul_eq_mul- Scalar multiplication of natural numbers coincides with ordinary multiplication.
Finset.sum_const- Summing a constant over a finite set equals the cardinality of the set times the constant.
Finset.sum_le_sum- If f(x) ≤ g(x) for all x in a finite set, the sum of f is at most the sum of g.
w3_assignment_card- The number of permutations extending an injective map on D is at most (n - |D|)!.
Nat.mul_le_mul_left- If a ≤ b, then c * a ≤ c * b.
Nat.mul_le_mul_right- If a ≤ b, then a * c ≤ b * c.
Nat.descFactorial_succ- The falling factorial satisfies n^{\underline{k+1}} = (n - k) * n^{\underline k}.
Nat.descFactorial_zero- The falling factorial of length 0 is 1.
Nat.sub_zero- Subtracting zero leaves a natural number unchanged.
Nat.sub_sub- Subtracting m then k equals subtracting m + k.
Nat.descFactorial_le_pow- The falling factorial n^{\underline k} is bounded above by n^k.
Nat.descFactorial_eq_factorial_mul_choose- The falling factorial satisfies n^{\underline k} = k! * \binom{n}{k}.
w3_mass_polynomial- For odd n ≥ 13, n * (12(n/2)(n-3)^{\underline 3} + 120(n/2)^3) < n^{\underline 6}.
Nat.choose_one_right- \binom{n}{1} = n for every natural number n.
Nat.mul_lt_mul_of_pos_left- If a < b and c > 0, then c * a < c * b.
Nat.factorial_pos- The factorial of any natural number is strictly positive.
w3_sel- Predicate defining which vertex blocks belong to selector j in Fin 3.
w3_positions- The set of vertices whose block index satisfies selector j.
w3_block- The canonical assignment of each vertex in Fin n to block 0, 1, or 2.
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying integers are equal.
Finset.card_biUnion_le- The cardinality of a union of finite sets is at most the sum of their cardinalities.
w3_closed_event_card- The number of permutations mapping D to a set closed under color i is at most |D|! * \binom{n/2}{|D|/2} * (n - |D|)!.
Fintype.sum_prod_type- A sum over a product of two finite types equals the iterated sum over each component.
w3_positions_card- For n ≥ 7, the size of positions(j) is 6 if j = 2, and 3 otherwise.
Fin.sum_univ_succ- A sum over Fin (n+1) splits as the term at 0 plus the sum over the remaining terms.
Finset.card_univ- The cardinality of the universal set of a finite type equals the type's cardinality.
Fintype.card_perm- The permutation group of a set of size n has cardinality n!.
Fintype.card_fin- The cardinality of Fin n is n.
w3_mass_lt- For odd n ≥ 13, the sum of bad permutation counts over all colors and block cuts is strictly less than n!.
lt_irrefl- Strict inequality is irreflexive: no element is strictly less than itself.
Finset.eq_univ_of_forall- A subset containing every element of a finite type is the entire universe.
Finset.mem_biUnion- An element belongs to a big union iff it belongs to one of the indexed members.
w3_avoid_blocks- There exists a permutation σ such that no block position set under σ is closed under any color.
Equiv.symm_apply_apply- Applying an equivalence and then its inverse is the identity.
w3_root- The canonical representative 3j of part j belongs to block j.
w3_cut_shape- Every non-trivial cut in a 3-element set is either a standard selector or its complement.
Finset.mem_image- An element is in the image of a set iff it is the value of some element in that set.
w3_mem_positions- A vertex belongs to positions(j) iff its block satisfies selector j.
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
w279_c_swap- Swapping the two endpoints of an edge does not change its color.
w279_missing_vertex_equiv- In a proper edge coloring of odd K_n with minimal colors, every color misses a unique vertex.
Fintype.card_congr- Equivalent finite types have equal cardinality.
w3_partition- For odd n ≥ 13, there exists a 3-partition with roots where every color crosses every cut.
simple_graph_wild_number_le_of_block_cut_condition- A graph coloring with a q-partition and roots where every color crosses every cut has wild number at most n - q.
Nat.exists_eq_succ_of_ne_zero- Every non-zero natural number is a successor of some natural number.
wsc_even_min_colors- For odd n ≥ 3, the chromatic number of the line graph of K_n is n.
wsc_restrict_color- Restricts an edge coloring of K_{m+1} to an edge coloring of the complete subgraph K_m.
wsc_missing_vertex_equiv_of_le- A proper edge coloring of odd K_m with at most m colors induces a bijection between colors and missing vertices.
wsc_color_used- Every color is used by at least one edge in a proper edge coloring of complete graphs with missing vertex bijection.
wsc_even_upper_of_partition- For even n, a 3-partition of the odd subgraph K_{n-1} crossing all cuts implies the wild number of K_n is at most n - 4.
- The arithmetic inequality in step 4 is verified via nonlinear arithmetic (`nlinarith`) on an expanded degree-6 polynomial.
- The cut classification lemma w3_cut_shape in step 7 is established by finite reflection (`decide +kernel`) over all subsets of Fin 3.
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.
set_option maxHeartbeats 1000000set_option maxRecDepth 100000variable {n : ℕ}open Classical inlemma w3_assignment_card (D : Finset (Fin n)) (f : Fin n → Fin n) (hf : Set.InjOn f (↑D : Set (Fin n))) : (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => ∀ x ∈ D, σ x = f x)).card ≤ (n-D.card).factorial := by classical have hi := permutation_partial_assignment_card_bound_of_switching D f hf (Finset.univ : Finset (Equiv.Perm (Fin n))) (by intro a ha σ hσ hσa y; exact Finset.mem_univ _) simp only [Fintype.card_fin, Finset.card_univ, Fintype.card_perm] at hi have hd : D.card ≤ n := by simpa using Finset.card_le_univ D have he := Nat.factorial_mul_descFactorial hd have hp : 0 < (n : ℕ).descFactorial D.card := Nat.descFactorial_pos.2 hd apply Nat.le_of_mul_le_mul_left (c := (n : ℕ).descFactorial D.card) (hc := hp) convert hi.trans_eq (he.symm.trans (Nat.mul_comm _ _)) using 1 congr 1 apply congrArg Finset.card ext σ simp only [Finset.mem_filter, Finset.mem_univ, true_and]open Classical inlemma w3_closed_event_card (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 : Finset (Fin n)) (i : Fin n) : (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i (D.image σ))).card ≤ D.card.factorial * Nat.choose (n/2) (D.card/2) * (n-D.card).factorial := by classical let A : Finset (Equiv.Perm (Fin n)) := Finset.univ.filter fun σ => w279_closed c i (D.image σ) let F : Finset (Fin n → Fin n) := Finset.univ.filter fun f => (∀ x ∉ D, f x = x) ∧ Set.InjOn f (↑D : Set (Fin n)) ∧ w279_closed c i (D.image f) let φ : Equiv.Perm (Fin n) → Fin n → Fin n := fun σ x => if x ∈ D then σ x else x have hmaps : ∀ σ ∈ A, φ σ ∈ F := by intro σ hσ simp only [F, Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨?_, ?_, ?_⟩ · intro x hx; simp only [φ, if_neg hx] · intro x hx y hy he change x ∈ D at hx change y ∈ D at hy dsimp only [φ] at he rw [if_pos hx, if_pos hy] at he exact σ.injective he · have he : D.image (φ σ) = D.image σ := by apply Finset.image_congr intro x hx change x ∈ D at hx simp only [φ, if_pos hx] rw [he] exact (Finset.mem_filter.1 hσ).2 have hF : F.card ≤ D.card.factorial * Nat.choose (n/2) (D.card/2) := by have hi := w279_count_events D (fun U => w279_closed c i U) have hc := w279_count_closed c m hm i D.card have hr : (w279_R c m i).card = n/2 := by have := w279_card_R c m hm i; omega rw [hr] at hc exact hi.trans (Nat.mul_le_mul_left _ hc) have hb : A.card ≤ F.card * (n-D.card).factorial := by rw [Finset.card_eq_sum_card_fiberwise (f := φ) (t := F) hmaps] rw [← smul_eq_mul, ← Finset.sum_const] refine Finset.sum_le_sum fun f hf => ?_ have hfi := (Finset.mem_filter.1 hf).2.2.1 refine (Finset.card_le_card ?_).trans (w3_assignment_card D f hfi) intro σ hσ rw [Finset.mem_filter] at hσ ⊢ refine ⟨Finset.mem_univ _, ?_⟩ intro x hx have he := congrFun hσ.2 x simpa only [φ, if_pos hx] using he exact hb.trans (Nat.mul_le_mul_right _ hF)lemma w3_mass_polynomial (n : ℕ) (hn : 13 ≤ n) (hodd : n % 2 = 1) : n*(12*(n/2)*(n-3).descFactorial 3+120*(n/2)^3) < n.descFactorial 6 := by obtain ⟨r,rfl⟩ : ∃ r : ℕ, n=2*r+13 := by exact ⟨(n-13)/2, by omega⟩ have hm : (2*r+13)/2 = r+6 := by omega rw [hm] norm_num only [Nat.descFactorial_succ, Nat.descFactorial_zero, Nat.sub_zero, Nat.sub_sub] simp only [show 2*r+13-1=2*r+12 by omega, show 2*r+13-2=2*r+11 by omega, show 2*r+13-3=2*r+10 by omega, show 2*r+13-4=2*r+9 by omega, show 2*r+13-5=2*r+8 by omega] have hp : 0 < (2*r+13)*2*(r+6)*(16*r^4+256*r^3+1448*r^2+3140*r+1440) := by positivity nlinarith only [hp]lemma w3_mass_lt (n : ℕ) (hn : 13 ≤ n) (hodd : n % 2 = 1) : n*(2*(3 : ℕ).factorial*Nat.choose (n/2) 1*(n-3).factorial+ (6 : ℕ).factorial*Nat.choose (n/2) 3*(n-6).factorial) < n.factorial := by have hc := Nat.descFactorial_le_pow (n/2) 3 rw [Nat.descFactorial_eq_factorial_mul_choose] at hc norm_num only [Nat.factorial_succ, Nat.factorial_zero] at hc have h1 := Nat.factorial_mul_descFactorial (n := n) (k := 6) (by omega : 6 ≤ n) have h2 := Nat.factorial_mul_descFactorial (n := n-3) (k := 3) (by omega : 3 ≤ n-3) simp only [Nat.sub_sub, show 3+3=6 by decide] at h2 have hp := w3_mass_polynomial n hn hodd calc _ ≤ (n-6).factorial * (n*(12*(n/2)*(n-3).descFactorial 3+120*(n/2)^3)) := by rw [← h2] norm_num only [Nat.factorial_succ, Nat.factorial_zero, Nat.choose_one_right] have hi := Nat.mul_le_mul_left (120*n*(n-6).factorial) hc nlinarith only [hi] _ < (n-6).factorial * n.descFactorial 6 := Nat.mul_lt_mul_of_pos_left hp (Nat.factorial_pos _) _ = _ := h1def w3_block (v : Fin n) : Fin 3 := if v.val<3 then 0 else if v.val<6 then 1 else 2def w3_sel (j b : Fin 3) : Prop := if j=0 then b=0 else if j=1 then b=1 else b≠2instance w3_sel_decidable (j b : Fin 3) : Decidable (w3_sel j b) := by unfold w3_sel; infer_instancedef w3_positions (j : Fin 3) : Finset (Fin n) := Finset.univ.filter fun v => w3_sel j (w3_block v)lemma w3_mem_positions (j : Fin 3) (v : Fin n) : v ∈ w3_positions j ↔ w3_sel j (w3_block v) := by simp [w3_positions]lemma w3_positions_card (hn : 7 ≤ n) (j : Fin 3) : (w3_positions (n := n) j).card = if j=2 then 6 else 3 := by have he0 : w3_positions (n := n) 0 = {⟨0,by omega⟩,⟨1,by omega⟩,⟨2,by omega⟩} := by ext v simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block, Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] split_ifs <;> omega have he1 : w3_positions (n := n) 1 = {⟨3,by omega⟩,⟨4,by omega⟩,⟨5,by omega⟩} := by ext v simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block, Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] split_ifs <;> omega have he2 : w3_positions (n := n) 2 = {⟨0,by omega⟩,⟨1,by omega⟩,⟨2,by omega⟩,⟨3,by omega⟩,⟨4,by omega⟩,⟨5,by omega⟩} := by ext v simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block, Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff] split_ifs <;> omega fin_cases j <;> norm_num [he0, he1, he2, Fin.ext_iff] change (w3_positions (n := n) 2).card = 6 rw [he2] norm_num [Fin.ext_iff]lemma w3_root (hn : 7 ≤ n) (j : Fin 3) : w3_block (⟨3*j.val, by have := j.isLt; omega⟩ : Fin n) = j := by fin_cases j <;> norm_num [w3_block, Fin.ext_iff]lemma w3_cut_shape : ∀ S : Finset (Fin 3), S.Nonempty → S ≠ Finset.univ → ∃ j : Fin 3, (∀ b : Fin 3, b ∈ S ↔ w3_sel j b) ∨ (∀ b : Fin 3, b ∈ S ↔ ¬w3_sel j b) := by decide +kernellemma w3_avoid_blocks (hn : 13 ≤ n) (hodd : n % 2 = 1) (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) : ∃ σ : Equiv.Perm (Fin n), ∀ (j : Fin 3) (i : Fin n), ¬w279_closed c i ((w3_positions j).image σ) := by classical let Bad : Fin 3 × Fin n → Finset (Equiv.Perm (Fin n)) := fun ji => Finset.univ.filter fun σ => w279_closed c ji.2 ((w3_positions (n := n) ji.1).image σ) let B : Finset (Equiv.Perm (Fin n)) := Finset.univ.biUnion Bad have hb : B.card ≤ n*(2*(3 : ℕ).factorial*Nat.choose (n/2) 1*(n-3).factorial+ (6 : ℕ).factorial*Nat.choose (n/2) 3*(n-6).factorial) := by refine Finset.card_biUnion_le.trans ?_ have hi : ∑ ji : Fin 3 × Fin n, (Bad ji).card ≤ ∑ ji : Fin 3 × Fin n, (w3_positions (n := n) ji.1).card.factorial * Nat.choose (n/2) ((w3_positions (n := n) ji.1).card/2) * (n-(w3_positions (n := n) ji.1).card).factorial := by exact Finset.sum_le_sum fun ji hji => w3_closed_event_card c m hm (w3_positions (n := n) ji.1) ji.2 refine hi.trans_eq ?_ rw [Fintype.sum_prod_type] simp only [w3_positions_card (by omega : 7 ≤ n)] norm_num [Fin.sum_univ_succ, Fin.ext_iff] ring have hlt : B.card < (Finset.univ : Finset (Equiv.Perm (Fin n))).card := by rw [Finset.card_univ, Fintype.card_perm, Fintype.card_fin] exact hb.trans_lt (w3_mass_lt n hn hodd) have hne : B ≠ Finset.univ := by intro he; rw [he] at hlt; exact lt_irrefl _ hlt have hex : ∃ σ : Equiv.Perm (Fin n), σ ∉ B := by by_contra h push Not at h exact hne (Finset.eq_univ_of_forall h) obtain ⟨σ,hσ⟩ := hex refine ⟨σ, ?_⟩ intro j i hi exact hσ (Finset.mem_biUnion.2 ⟨(j,i), Finset.mem_univ _, Finset.mem_filter.2 ⟨Finset.mem_univ _,hi⟩⟩)lemma w3_partition (hn : 13 ≤ n) (hodd : n % 2 = 1) (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) : ∃ (p : Fin n → Fin 3) (roots : Fin 3 → Fin n), (∀ t, p (roots t) = t) ∧ ∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin 3)), S.Nonempty → S ≠ Finset.univ → ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e := by classical obtain ⟨σ,hσ⟩ := w3_avoid_blocks hn hodd c m hm refine ⟨(fun v => w3_block (σ.symm v)), (fun j => σ ⟨3*j.val, by have := j.isLt; omega⟩), ?_, ?_⟩ · intro j simpa only [Equiv.symm_apply_apply] using w3_root (by omega : 7 ≤ n) j · intro e S hS hSu by_contra hno push Not at hno obtain ⟨j,hj | hj⟩ := w3_cut_shape S hS hSu · apply hσ j (c e) intro u hu v huv hc obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu have hxu := (w3_mem_positions j x).1 hx by_contra hv have hxS := (hj _).2 hxu have hvS : w3_block (σ.symm v) ∉ S := by intro hvS apply hv exact Finset.mem_image.2 ⟨σ.symm v, (w3_mem_positions _ _).2 ((hj _).1 hvS), by simp⟩ exact hno (σ x) v huv (by simpa using hxS) hvS hc · apply hσ j (c e) intro u hu v huv hc obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu have hxu := (w3_mem_positions j x).1 hx by_contra hv have hxS : w3_block (σ.symm (σ x)) ∉ S := by intro hh exact (hj _).1 (by simpa using hh) hxu have hvS : w3_block (σ.symm v) ∈ S := by apply (hj _).2 intro hvj exact hv (Finset.mem_image.2 ⟨σ.symm v, (w3_mem_positions _ _).2 hvj, by simp⟩) exact hno v (σ x) (Ne.symm huv) hvS hxS ((w279_c_swap c huv).symm.trans hc)theorem wild_number_complete_graph_upper_sub_four_add_parity (n k : ℕ) (hn : 13 ≤ n) (hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) : simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c ≤ n-4+n%2 := by by_cases hodd : n%2=1 · obtain ⟨m,hm⟩ := w279_missing_vertex_equiv n k (by omega) hodd hk c have hk' : k=n := by simpa using Fintype.card_congr m subst k obtain ⟨p,roots,hr,hc⟩ := w3_partition hn hodd c m hm have hu := simple_graph_wild_number_le_of_block_cut_condition (n := n) (q := 3) (by omega) c p roots hr hc omega · obtain ⟨m,rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0) have hm13 : 13 ≤ m := by omega have hmOdd : m%2=1 := by omega have hk' : k=m := wsc_even_min_colors (by omega) hmOdd hk c subst k let cc := wsc_restrict_color c obtain ⟨miss,hmiss⟩ := wsc_missing_vertex_equiv_of_le m m (by omega) hmOdd le_rfl cc obtain ⟨p,roots,hr,hcuts⟩ := w3_partition hm13 hmOdd cc miss hmiss have hc : ∀ (i : Fin m) (S : Finset (Fin 3)), S.Nonempty → S ≠ Finset.univ → ∃ (u v : Fin m) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ cc ⟨s(u,v),wild_kn_mem huv⟩ = i := by intro i S hS hSu obtain ⟨e,he⟩ := wsc_color_used (by omega) cc miss hmiss i obtain ⟨u,v,huv,hu,hv,hcol⟩ := hcuts e S hS hSu exact ⟨u,v,huv,hu,hv,hcol.trans he⟩ have hu := wsc_even_upper_of_partition (by omega) c p roots hr hc omega