wild_number_complete_graph_large_odd_multiple_three_eq
For every odd integer q>=100001, every natural number k equal to the chromatic number of the line graph of the complete graph K_(3q), and every proper edge coloring c of K_(3q) with colors Fin k, the wild number equals 2q. Equivalently, the conjectured equality holds for every n>=300003 with n congruent to 3 modulo 6, for every minimum proper edge coloring.
Statement
theorem wild_number_complete_graph_large_odd_multiple_three_eq (q k : ℕ)
(hq : 100001 ≤ q) (hodd : q % 2 = 1)
(hk : (⊤ : SimpleGraph (Fin (3 * q))).lineGraph.chromaticNumber = k)
(c : (⊤ : SimpleGraph (Fin (3 * q))).lineGraph.Coloring (Fin k)) :
simple_graph_wild_number (⊤ : SimpleGraph (Fin (3 * q))) c = 2 * q- Related work
- arXiv:2610.22142, Section 6 conjecture and Theorems 3.4 and 3.5 (the paper proves equality for 3<=n<=12); existing AFTD case n=279. Uniform permutation-event argument with elementary binomial bounds extends equality to an infinite family. Literature checked 2026-10-28 at https://arxiv.org/abs/2610.22142 and searches for the paper title, wild number minimum proper coloring, and wild number 279.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- wild_triple_partition_mass_criterionFor an odd number q of triple blocks, q>=3, a proper edge coloring of K_(3q) with 3q colors and a bijection between colors and their…
- wild_triple_partition_large_order_mass_boundFor odd q>=100001, both canonical seal-event resource sums for q triples of vertices in K_(3q), with weight (21/20)^d/(3q)_d, are at most…
- 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⌋.
- 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…
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
Read back from the Lean
For any natural numbers $q$ and $k$ such that $q \ge 100001$ and $q$ is odd ($q \bmod 2 = 1$), if $k$ is the chromatic number of the line graph of the complete graph on $\mathrm{Fin}(3q)$ (that is, the chromatic index of $K_{3q}$), then for every proper coloring $c$ of the line graph of the complete graph on $\mathrm{Fin}(3q)$ using $k$ colors (i.e., every proper edge-coloring of $K_{3q}$ with $k$ colors), the wild number of the complete graph on $\mathrm{Fin}(3q)$ with respect to $c$ is equal to $2q$.
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 proves that the wild number of any minimum proper edge coloring of the complete graph $K_{3q}$ equals $2q$, for every odd integer $q \ge 100001$. The argument proceeds by establishing matching upper and lower bounds. A general complete-graph lower bound gives $\mathrm{wild\_number} \ge \lfloor \frac{4}{3} \lfloor \frac{3q+1}{2} \rfloor \rfloor = 2q$ via integer arithmetic for odd $q$. For the upper bound, every color class in a minimum edge coloring leaves exactly one vertex uncovered, inducing a bijection between colors and vertices, and an analytic mass criterion on triple partitions bounds the wild number from above by $2q$.
Each color in the edge coloring is omitted at exactly one vertex, providing an equivalence $m : \mathrm{Fin}(k) \simeq \mathrm{Fin}(3q)$.
Since $q \ge 100001$ is odd, the complete graph $K_{3q}$ has odd order $3q \ge 3$, which is checked by linear arithmetic (`omega`). Lemma `w279_missing_vertex_equiv` applies to any minimum proper edge coloring $c$ of $K_{3q}$, yielding an equivalence $m$ between color indices $\mathrm{Fin}(k)$ and vertices $\mathrm{Fin}(3q)$ such that vertex $v$ misses color $i$ if and only if $v = m(i)$.
uses
w279_missing_vertex_equivobtain ⟨m, hm⟩ := w279_missing_vertex_equiv (3 * q) k (by omega) (by omega) hk c
The number of colors $k$ equals $3q$.
Because $m$ is an equivalence between $\mathrm{Fin}(k)$ and $\mathrm{Fin}(3q)$, their cardinalities must coincide by `Fintype.card_congr`, establishing $k = 3q$. Substituting $k = 3q$ replaces $k$ with $3q$ throughout the context.
uses
Fintype.card_congrhave hk' : k = 3 * q := by simpa using Fintype.card_congr m subst k
The wild number of $c$ on $K_{3q}$ is at most $2q$.
Since $q \ge 100001$ is odd, lemma `wild_triple_partition_large_order_mass_bound` ensures that both the pair and vertex mass sums for triple partitions are at most $1/50$. Because $q \ge 3$ (verified by `omega`) and $q$ is odd, lemma `wild_triple_partition_mass_criterion` applies to the coloring $c$ and the missing-vertex bijection $m$, establishing the upper bound $\mathrm{wild\_number}(K_{3q}, c) \le 2q$.
uses
wild_triple_partition_large_order_mass_bound,wild_triple_partition_mass_criterionobtain ⟨hp, hv⟩ := wild_triple_partition_large_order_mass_bound q hq hodd have hu := wild_triple_partition_mass_criterion (by omega : 3 ≤ q) hodd hp hv c m hm
The wild number of $c$ on $K_{3q}$ is at least $2q$.
Lemma `wild_number_complete_graph_min_proper_coloring_ge` establishes a general lower bound $\lfloor \frac{4}{3} \lfloor \frac{n+1}{2} \rfloor \rfloor \le \mathrm{wild\_number}$ for any minimum proper edge coloring of $K_n$ ($n \ge 3$). For $n = 3q$ with $q$ odd, integer division arithmetic (`omega`) simplifies $\lfloor \frac{4}{3} \lfloor \frac{3q+1}{2} \rfloor \rfloor$ to $2q$. Rewriting with this equality yields $2q \le \mathrm{wild\_number}(K_{3q}, c)$.
uses
wild_number_complete_graph_min_proper_coloring_gehave hl := wild_number_complete_graph_min_proper_coloring_ge (3 * q) (3 * q) (by omega) hk c have he : 4 * ((3 * q + 1) / 2) / 3 = 2 * q := by omega rw [he] at hl
The wild number of $c$ on $K_{3q}$ is equal to $2q$.
Combining the upper bound $\mathrm{wild\_number}(K_{3q}, c) \le 2q$ and the lower bound $2q \le \mathrm{wild\_number}(K_{3q}, c)$ by antisymmetry of the ordering (`le_antisymm`) completes the proof.
uses
le_antisymmexact le_antisymm hu hl
w279_missing_vertex_equiv- In any minimum proper edge coloring of an odd complete graph $K_n$ ($n \ge 3$) with $k$ colors, each color is omitted at exactly one vertex, yielding an equivalence between the color set $\mathrm{Fin}(k)$ and the vertex set $\mathrm{Fin}(n)$.
Fintype.card_congr- An equivalence between two finite types implies that they have the same cardinality.
wild_triple_partition_large_order_mass_bound- For any odd integer $q \ge 100001$, both the pair mass sum and the vertex mass sum for triple partitions are at most $1/50$.
wild_triple_partition_mass_criterion- For an odd order parameter $q \ge 3$, if both the pair and vertex mass bounds are at most $1/50$ and the edge coloring satisfies the missing-vertex equivalence, then the wild number of $K_{3q}$ under this coloring is at most $2q$.
wild_number_complete_graph_min_proper_coloring_ge- For any complete graph $K_n$ ($n \ge 3$) and any minimum proper edge coloring with $k$ colors, the wild number is bounded below by $\lfloor \frac{4}{3} \lfloor \frac{n+1}{2} \rfloor \rfloor$.
le_antisymm- In any partially ordered type, if $a \le b$ and $b \le a$, then $a = b$.
- The lower bound relies on integer division arithmetic in `omega` to evaluate $\lfloor \frac{4}{3} \lfloor \frac{3q+1}{2} \rfloor \rfloor = 2q$ for odd $q$.
- The upper bound relies on `wild_triple_partition_large_order_mass_bound`, which encapsulates large-order analytic bounds on partition mass sums from the knowledge base.
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.
theorem wild_number_complete_graph_large_odd_multiple_three_eq (q k : ℕ) (hq : 100001 ≤ q) (hodd : q % 2 = 1) (hk : (⊤ : SimpleGraph (Fin (3 * q))).lineGraph.chromaticNumber = k) (c : (⊤ : SimpleGraph (Fin (3 * q))).lineGraph.Coloring (Fin k)) : simple_graph_wild_number (⊤ : SimpleGraph (Fin (3 * q))) c = 2 * q := by obtain ⟨m, hm⟩ := w279_missing_vertex_equiv (3 * q) k (by omega) (by omega) hk c have hk' : k = 3 * q := by simpa using Fintype.card_congr m subst k obtain ⟨hp, hv⟩ := wild_triple_partition_large_order_mass_bound q hq hodd have hu := wild_triple_partition_mass_criterion (by omega : 3 ≤ q) hodd hp hv c m hm have hl := wild_number_complete_graph_min_proper_coloring_ge (3 * q) (3 * q) (by omega) hk c have he : 4 * ((3 * q + 1) / 2) / 3 = 2 * q := by omega rw [he] at hl exact le_antisymm hu hl