wild_odd_sharpness_of_weighted_cubic_cost
At any positive odd complete-graph order n>=3, for any minimum proper coloring and any finite family of rooted floor(n/3)-block partitions with block sizes at least three, let d count colors failing to cross some proper nonempty block cut. If nonnegative real weights give a strictly negative sum of w*(d-1)*(d-3)*(d-4), the wild number equals the conjectured formula. The strict weighted inequality is a hypothesis, not a proved universal estimate.
Statement
theorem wild_odd_sharpness_of_weighted_cubic_cost {J : Type*} [Fintype J] {n k : ℕ} (hn : 3≤n) (hodd : n%2=1) (hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber=k) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (p : J → Fin n → Fin (n/3)) (root : J → Fin (n/3) → Fin n) (hroot : ∀ j t,p j (root j t)=t) (hmin : ∀ j t,3≤(univ.filter fun v => p j v=t).card) (w : J → ℝ) (hw : ∀ j,0≤w j) (h : let D : J → Finset (Fin k) := fun j => univ.filter fun i => ∃ S : Finset (Fin (n/3)),S.Nonempty ∧ S≠univ ∧ ∀ u v (huv : u≠v),p j u∈S → p j v∉S → c ⟨s(u,v),wild_kn_mem huv⟩≠i let d : J → ℕ := fun j => (D j).card (∑ j,w j*((d j : ℝ)-1)*((d j : ℝ)-3)*((d j : ℝ)-4))<0) : simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c=4*((n+1)/2)/3
- Source
- IN-342 resumed helper for OP-306, arXiv:2610.22142 Sections3.3.2 and6. This is a weighted interface to the existing finite/adaptive cubic avoidance route. The new proposed square-polynomial weighting of invalid-color counts is tested only in experiments8807,8812,8822,8824. No uniform inequality, novel wild-number bound, or research advance is asserted by this conditional helper.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- finite_avoidance_of_weighted_cubic_costFor any natural-valued defect function on a finite sample space and any nonnegative real weights, a strictly negative weighted sum of…
- wild_number_complete_odd_eq_iff_optimal_partitionFor every minimum proper coloring of K_n at odd order n>=3, its wild number equals floor(4*ceil(n/2)/3) if and only if there is a rooted…
- 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.
The proof, explained
The proof establishes that the wild number of an odd complete graph K_n (n ≥ 3) under a minimum edge coloring equals 4*⌊(n+1)/2⌋/3 by exhibiting an optimal rooted block partition. First, because the cubic polynomial (x-1)(x-3)(x-4) is nonnegative on all positive integers x ≥ 1, the strict negativity of the weighted sum forces the defect count d(j) to equal 0 for some partition p j in the family. A characterization theorem then reduces the wild number equality to showing that every edge color crosses every proper nonempty block cut of p j. Finally, if any color failed to cross some cut, that color would belong to the defect set D(j), giving d(j) > 0 and contradicting d(j) = 0.
There exists an index j ∈ J such that d(j) = 0, meaning that no color fails to cross any proper nonempty block cut of partition p j.
We define D(j) to be the set of colors that fail to cross some proper nonempty block cut S under partition p j, and let d(j) = |D(j)|. The polynomial (x - 1)(x - 3)(x - 4) is nonnegative for every natural number x ≥ 1: it evaluates to 0 at x ∈ {1, 3, 4}, evaluates to 2 > 0 at x = 2, and is strictly positive for all x ≥ 5. Since all weights w j are nonnegative, the weighted cubic sum can only be strictly negative if d(j) = 0 for some j. The lemma finite_avoidance_of_weighted_cubic_cost provides such an index j.
uses
finite_avoidance_of_weighted_cubic_costclassical let D : J → Finset (Fin k) := fun j => univ.filter fun i => ∃ S : Finset (Fin (n/3)),S.Nonempty ∧ S≠univ ∧ ∀ u v (huv : u≠v),p j u∈S → p j v∉S → c ⟨s(u,v),wild_kn_mem huv⟩≠i let d : J → ℕ := fun j => (D j).card obtain ⟨j,hj⟩ := finite_avoidance_of_weighted_cubic_cost d w hw h
To show that the wild number equals 4*⌊(n+1)/2⌋/3, it suffices to prove that under partition p j, every edge color crosses every proper nonempty cut of blocks.
By wild_number_complete_odd_eq_iff_optimal_partition, the wild number of K_n under c achieves the value 4*⌊(n+1)/2⌋/3 if and only if there exists a rooted partition into ⌊n/3⌋ blocks of size at least 3 whose cuts are all crossed by edges of every color. We instantiate this criterion with the partition p j and roots root j obtained from the previous step; the rooting identity hroot and the minimum block size condition hmin are satisfied by hypothesis.
uses
wild_number_complete_odd_eq_iff_optimal_partitionapply (wild_number_complete_odd_eq_iff_optimal_partition hn hodd hk c).mpr refine ⟨p j,root j,hroot j,hmin j,?_⟩
Assuming for contradiction that some edge e and some proper nonempty cut S have no crossing edge of color c(e), every pair of vertices across the cut forms an edge of color distinct from c(e).
We fix an edge e and a nonempty proper subset of blocks S. We suppose for contradiction that no two vertices u with p j(u) ∈ S and v with p j(v) ∉ S form an edge with color c(e). Under this assumption, every crossing edge (u, v)—which is a valid edge of the complete graph by wild_kn_mem—must have a color distinct from c(e).
uses
wild_kn_memintro e S hS hS' by_contra hnot have hno : ∀ u v (huv : u≠v),p j u∈S → p j v∉S → c ⟨s(u,v),wild_kn_mem huv⟩≠c e := by intro u v huv hu hv hc exact hnot ⟨u,v,huv,hu,hv,hc⟩
The assumed failure implies c(e) ∈ D(j), which makes d(j) > 0 and contradicts d(j) = 0.
Because the cut S witnesses that color c(e) does not cross S, the color c(e) satisfies the condition defining D(j). Hence c(e) ∈ D(j) by mem_filter.mpr and mem_univ. Since D(j) contains c(e), its cardinality d(j) is strictly positive by card_pos.mpr. But d(j) = 0 from the choice of j, and Nat.ne_of_gt turns 0 < d(j) into d(j) ≠ 0, producing a contradiction.
uses
mem_filter.mpr,mem_univ,card_pos.mpr,Nat.ne_of_gthave hi : c e∈D j := mem_filter.mpr ⟨mem_univ _,S,hS,hS',hno⟩ have hpos : 0<(D j).card := card_pos.mpr ⟨c e,hi⟩ exact (Nat.ne_of_gt hpos) hj
finite_avoidance_of_weighted_cubic_cost- If a weighted sum of (d(j)-1)*(d(j)-3)*(d(j)-4) with nonnegative weights is strictly negative for a natural-valued function d, then d(j) = 0 for at least one index j.
wild_number_complete_odd_eq_iff_optimal_partition- For an odd complete graph of order n ≥ 3 and a minimum edge coloring c with k colors, the wild number equals 4*⌊(n+1)/2⌋/3 if and only if there exists a rooted partition into ⌊n/3⌋ blocks of size at least 3 such that every edge color crosses every proper nonempty cut of blocks.
wild_kn_mem- Any two distinct vertices u ≠ v in a complete graph span an edge.
mem_filter.mpr- An element belongs to a filtered finset if it belongs to the base finset and satisfies the filtering predicate.
mem_univ- Every element of a finite type belongs to the universal finset univ.
card_pos.mpr- A finset has strictly positive cardinality if and only if it is nonempty.
Nat.ne_of_gt- If b < a for natural numbers, then a ≠ b.
- The strict weighted cubic inequality is taken as an explicit hypothesis in the theorem rather than a universally proved estimate.
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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 2000000theorem wild_odd_sharpness_of_weighted_cubic_cost {J : Type*} [Fintype J] {n k : ℕ} (hn : 3≤n) (hodd : n%2=1) (hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber=k) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (p : J → Fin n → Fin (n/3)) (root : J → Fin (n/3) → Fin n) (hroot : ∀ j t,p j (root j t)=t) (hmin : ∀ j t,3≤(univ.filter fun v => p j v=t).card) (w : J → ℝ) (hw : ∀ j,0≤w j) (h : let D : J → Finset (Fin k) := fun j => univ.filter fun i => ∃ S : Finset (Fin (n/3)),S.Nonempty ∧ S≠univ ∧ ∀ u v (huv : u≠v),p j u∈S → p j v∉S → c ⟨s(u,v),wild_kn_mem huv⟩≠i let d : J → ℕ := fun j => (D j).card (∑ j,w j*((d j : ℝ)-1)*((d j : ℝ)-3)*((d j : ℝ)-4))<0) : simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c=4*((n+1)/2)/3 := by classical let D : J → Finset (Fin k) := fun j => univ.filter fun i => ∃ S : Finset (Fin (n/3)),S.Nonempty ∧ S≠univ ∧ ∀ u v (huv : u≠v),p j u∈S → p j v∉S → c ⟨s(u,v),wild_kn_mem huv⟩≠i let d : J → ℕ := fun j => (D j).card obtain ⟨j,hj⟩ := finite_avoidance_of_weighted_cubic_cost d w hw h apply (wild_number_complete_odd_eq_iff_optimal_partition hn hodd hk c).mpr refine ⟨p j,root j,hroot j,hmin j,?_⟩ intro e S hS hS' by_contra hnot have hno : ∀ u v (huv : u≠v),p j u∈S → p j v∉S → c ⟨s(u,v),wild_kn_mem huv⟩≠c e := by intro u v huv hu hv hc exact hnot ⟨u,v,huv,hu,hv,hc⟩ have hi : c e∈D j := mem_filter.mpr ⟨mem_univ _,S,hS,hS',hno⟩ have hpos : 0<(D j).card := card_pos.mpr ⟨c e,hi⟩ exact (Nat.ne_of_gt hpos) hj