AFTD Auto-Formalizing Theoretical Domains

wild_odd_sharpness_of_weighted_cubic_cost

theoremverified

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

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.

  1. 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.

    lines 20–26

    uses finite_avoidance_of_weighted_cubic_cost

      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
  2. 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.

    lines 27–28

    uses wild_number_complete_odd_eq_iff_optimal_partition

      apply (wild_number_complete_odd_eq_iff_optimal_partition hn hodd hk c).mpr
      refine ⟨p j,root j,hroot j,hmin j,?_⟩
  3. 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).

    lines 29–34

    uses wild_kn_mem

      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⟩
  4. 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.

    lines 35–37

    uses mem_filter.mpr, mem_univ, card_pos.mpr, Nat.ne_of_gt

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it