wild_odd_sharpness_of_adaptive_cubic_moments
For any minimum proper coloring at odd order n>=3 and any finite family of rooted partitions into floor(n/3) blocks of size at least three, count the colors failing to cross some proper nonempty block cut. If these counts satisfy the adaptive cubic strict moment criterion for some positive integer r, the wild number equals the conjectured floor(4*ceil(n/2)/3).
Statement
theorem wild_odd_sharpness_of_adaptive_cubic_moments {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) (r : ℕ) (hr : 1 ≤ r) (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 (r : ℝ) * (r + 1) * (∑ j, (d j : ℝ)) + 6 * (∑ j, ((d j).choose 3 : ℝ)) < (r : ℝ) * (r + 1) * Fintype.card J + (4 * (r : ℝ) - 2) * (∑ j, ((d j).choose 2 : ℝ))) : simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 4 * ((n + 1) / 2) / 3
- Source
- OP-306 / IN-338 general-route helpers for the strict prescribed-coloring conjecture in arXiv:2610.22142, Sections3.3.2 and6. Structural analysis of binary factorizations and exact finite averaging in experiments8399,8400,8402,8414. These are conditional certificate or method-diagnostic lemmas, not a new wild-number bound or research advance.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- finite_avoidance_of_adaptive_cubic_momentsFor a natural-valued defect count d on any finite sample space and any positive integer r, put R=r(r+1). If R times sum(d) plus6 times…
- 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…
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- 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 proof establishes sharpness of the wild number by finding an optimal block partition in the given family. By the finite avoidance lemma for adaptive cubic moments, the moment inequality guarantees the existence of a partition $p(j)$ with defect count zero, meaning that every color crosses every proper nonempty block cut. Applying the characterization theorem relating the wild number of complete graphs of odd order to optimal partitions, this defect-free partition witnesses that the wild number equals $4 \lfloor (n+1)/2 \rfloor / 3$.
There exists an index $j \in J$ whose associated partition $p(j)$ has no defect colors, so $d(j) = |D(j)| = 0$.
We define $D(j)$ as the finset of colors that fail to cross some proper nonempty block cut $S \subset \{0, \dots, \lfloor n/3 \rfloor - 1\}$, and set $d(j) = |D(j)|$. The hypothesis $h$ states that the counts $d(j)$ satisfy the adaptive cubic strict moment inequality with parameter $r \ge 1$. Applying the moment avoidance lemma `finite_avoidance_of_adaptive_cubic_moments` directly yields an index $j \in J$ such that $d(j) = 0$.
uses
finite_avoidance_of_adaptive_cubic_momentsclassical 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_adaptive_cubic_moments d r hr h
To show that the wild number of $(K_n, c)$ equals $4 \lfloor (n+1)/2 \rfloor / 3$, it suffices to show that for every edge $e$ and every proper nonempty block cut $S$, some edge crossing $S$ has color $c(e)$ under partition $p(j)$.
By `wild_number_complete_odd_eq_iff_optimal_partition`, the wild number of $K_n$ at odd order under coloring $c$ attains the target value if and only if there exists a valid rooted partition into $\lfloor n/3 \rfloor$ blocks of size at least 3 such that every edge color crosses every proper nonempty block cut. We instantiate this characterization with partition $p(j)$ and root map $\text{root}(j)$. The partition is rooted by hypothesis `hroot j` and has blocks of size at least 3 by hypothesis `hmin j`, leaving only the cut-crossing property to be established.
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, ?_⟩
For every edge $e$ and every proper nonempty block subset $S$, there exists an edge crossing $S$ with color $c(e)$.
We argue by contradiction: fix an edge $e$ and a proper nonempty block subset $S$, and suppose that no edge crossing $S$ has color $c(e)$. This means that for any distinct vertices $u$ and $v$ with $p(j)(u) \in S$ and $p(j)(v) \notin S$, the edge color $c(\{u, v\})$ is different from $c(e)$ (using `wild_kn_mem`). By the definition of $D(j)$, the set $S$ witnesses that $c(e) \in D(j)$ (using `mem_filter.mpr` and `mem_univ`). Consequently, $D(j)$ is nonempty, so its cardinality is strictly positive by `card_pos.mpr`. However, $d(j) = |D(j)| = 0$ from the choice of $j$, which contradicts positivity by `Nat.ne_of_gt`.
uses
wild_kn_mem,mem_univ,mem_filter.mpr,card_pos.mpr,Nat.ne_of_gtintro 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
finite_avoidance_of_adaptive_cubic_moments- If a family of non-negative integer counts $d(j)$ indexed by a finite set $J$ satisfies the adaptive cubic strict moment inequality for some integer $r \ge 1$, then there exists an index $j \in J$ with $d(j) = 0$.
wild_number_complete_odd_eq_iff_optimal_partition- For an odd integer $n \ge 3$ and a proper edge coloring $c$ of the complete graph $K_n$ using the minimum number of colors $k$, the wild number equals $4 \lfloor (n+1)/2 \rfloor / 3$ if and only if there exists a rooted partition of the vertices into $\lfloor n/3 \rfloor$ blocks of size at least 3 such that every edge color appears on at least one edge crossing every proper nonempty subset of blocks.
wild_kn_mem- In the complete graph on $n$ vertices, any pair of distinct vertices forms an edge.
mem_univ- Every element of a finite type belongs to its universal finset.
mem_filter.mpr- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
card_pos.mpr- A finset has strictly positive cardinality if and only if it is nonempty.
Nat.ne_of_gt- If a natural number is strictly greater than another, then the two numbers are not equal.
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 BigOperators Classicalset_option maxHeartbeats 2500000theorem wild_odd_sharpness_of_adaptive_cubic_moments {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) (r : ℕ) (hr : 1 ≤ r) (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 (r : ℝ) * (r + 1) * (∑ j, (d j : ℝ)) + 6 * (∑ j, ((d j).choose 3 : ℝ)) < (r : ℝ) * (r + 1) * Fintype.card J + (4 * (r : ℝ) - 2) * (∑ j, ((d j).choose 2 : ℝ))) : 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_adaptive_cubic_moments d r hr 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