Sharpness of the Wild Number Lower Bound for Minimum Proper Colorings of Complete Graphs of Order at Least 30000001
medium tier2026-10-28OP-306reviewed by Claude Code中文版
Abstract
Let $n \ge 3$ and let $\rho$ be a minimum proper edge coloring of the complete graph $K_n$. arXiv:2610.22142 proves $\operatorname{wld}_\rho(K_n) \ge \lfloor 4\lceil n/2\rceil/3 \rfloor$, shows that equality holds for $3 \le n \le 12$, and conjectures equality for every $n \ge 3$. We prove the conjecture for every $n \ge 30000001$. For odd $n$ we partition the vertices into $q = \lfloor n/3 \rfloor$ blocks of three or four vertices; joining every vertex to a root of its block gives $n - q$ edges, and these form a color-connecting set as soon as no nonempty proper union of blocks is closed under a color class. A partition with this property exists by a lopsided local lemma for random permutations: once $q \ge 10^7$, the weighted count of bad events through any one position or any one vertex is at most $1/50$. For even $n$ the extra vertex becomes a block of its own, which recovers the paper's reduction from $K_n$ to $K_{n-1}$. The whole proof is verified in Lean 4.
1. Introduction
Let $\gamma$ be an edge coloring of a graph $G$. A set $W$ of edges is color-connecting if, for every color $c_i$, the spanning subgraph whose edges are the edges of color $c_i$ together with $W$ is connected. The wild number $\operatorname{wld}_\gamma(G)$ is the minimum size of a color-connecting set. The paper arXiv:2610.22142 studies this parameter for complete and complete bipartite graphs.
For minimum proper edge colorings of $K_n$, that is, proper colorings with $\chi'(K_n)$ colors ($n$ colors for odd $n$, $n-1$ for even $n$), Theorem 3.4 of arXiv:2610.22142 proves $$\operatorname{wld}_\rho(K_n) \ge \left\lfloor \frac{4\lceil n/2\rceil}{3} \right\rfloor \qquad (n \ge 3),$$ Theorem 3.5 shows that this bound is attained for $3 \le n \le 12$, and Section 6 conjectures that it is attained for every $n \ge 3$ and every minimum proper coloring.
The paper also reduces the upper bound to a partition problem. When $n$ is odd, each color class $M_i$ is a near-perfect matching that misses one vertex $v_i$. Given a partition $P$ of the vertices into blocks of size at least three, a spanning tree in each block gives a set $W$ with $n - |P|$ edges, and Section 3.3.2 shows that $W$ is color-connecting if and only if $P$ is seal-free: no color class $M_i$ perfectly matches a nonempty union of blocks avoiding $v_i$. Writing $n = 3q + a$ with $a \in \{0,1,2\}$, a seal-free partition into $q$ blocks, namely $q - a$ triples and $a$ blocks of four, gives $n - q$ edges, which equals $\lfloor 4\lceil n/2\rceil/3 \rfloor$. For even orders, Section 3.3.3 shows $\operatorname{wld}_\rho(K_{2k}) \le \operatorname{wld}_{\rho_v}(K_{2k-1})$, where $\rho_v$ is the restriction to $K_{2k} - v$. The paper builds seal-free partitions by hand for small $n$. Beyond $n = 12$ the only instance settled before was $n = 279$ (wild_number_complete_graph_279_min_proper_coloring_eq), by an exact certificate for that single order.
We prove the conjecture for every $n \ge 30000001$ (wild_number_complete_graph_large_eq). The new ingredient is an existence proof for seal-free partitions at every large order. A uniformly random permutation of the vertices places them into the blocks of a fixed partition shape. Each potential seal is an event of the form "the permutation maps the positions of $h$ blocks onto a given set closed under a color". A lopsided local lemma for random permutations shows that, with high enough $q$, some permutation avoids all these events.
2. Preliminaries
Definition 1 (Minimum proper edge colorings). For $n \ge 1$ the complete graph $K_n$ is the complete simple graph on $\operatorname{Fin} n$. A proper edge coloring with color set $\operatorname{Fin} k$ is a proper vertex coloring of the line graph of $K_n$. It is minimum when $k$ is the chromatic number of the line graph, $\chi'(K_n)$; this equals $n$ for odd $n \ge 3$ and $n - 1$ for even $n$.
Definition 2 (Wild number). For a graph $G$ and an edge coloring $\gamma$, a set $W$ of edges is color-connecting if for every color $c$ used by $\gamma$ the spanning subgraph with edge set $\gamma^{-1}(c) \cup W$ is connected. The wild number simple_graph_wild_number is the infimum of the sizes $|W|$ of finite color-connecting sets. On $\mathbb{N}$ the infimum of the empty set is $0$, but for the complete graphs considered here the full edge set is color-connecting, so the infimum is a minimum.
Definition 3 (Block partitions and the cut condition). A block partition of $K_n$ into $q$ blocks is a map $p : \operatorname{Fin} n \to \operatorname{Fin} q$ with roots $r : \operatorname{Fin} q \to \operatorname{Fin} n$ such that $p(r(i)) = i$. A coloring $\gamma$ satisfies the block cut condition for $p$ if for every edge $e$ and every nonempty set $S \subsetneq \operatorname{Fin} q$ of blocks there is an edge $uv$ with $p(u) \in S$, $p(v) \notin S$ and $\gamma(uv) = \gamma(e)$.
Definition 4 (Seal events and weights). Fix a block map $b : \operatorname{Fin} n \to \operatorname{Fin} q$ and a proper coloring $c$ with $n$ colors. For a set $T$ of blocks, let $\operatorname{pos}(T) = b^{-1}(T)$. A seal event is a triple $(i, T, f)$ with $1 \le |T| \le \lfloor q/2 \rfloor$ and $f$ an injection of $\operatorname{pos}(T)$ into the vertices whose image is closed under color $i$: every edge of color $i$ with one endpoint in the image has both endpoints there. A permutation $\sigma$ of the vertices realizes the event if $\sigma = f$ on $\operatorname{pos}(T)$. For $d = |\operatorname{pos}(T)|$ the event gets the weight $$\operatorname{wt}_n(d) = \frac{(21/20)^d}{(n)_d}, \qquad (n)_d = n(n-1)\cdots(n-d+1).$$ A uniformly random permutation realizes a given event with probability exactly $1/(n)_d$.
Conventions. In Lean, division of natural numbers is floor division. The value $\lfloor 4\lceil n/2\rceil/3 \rfloor$ is written 4*((n+1)/2)/3, and $(n+1)/2 = \lceil n/2\rceil$ for every $n$.
3. Main result
Theorem (wild_number_complete_graph_large_eq). Let $n \ge 30000001$, let $k = \chi'(K_n)$ (the chromatic number of the line graph of $K_n$), and let $c$ be a proper edge coloring of $K_n$ with colors $\operatorname{Fin} k$. Then $$\operatorname{wld}_c(K_n) = \left\lfloor \frac{4\lceil n/2\rceil}{3} \right\rfloor .$$
In Lean the hypotheses are 30000001 ≤ n, the equation between the chromatic number of the line graph of the complete graph on Fin n and k, and a coloring c of that line graph by Fin k. The conclusion is simple_graph_wild_number ⊤ c = 4*((n+1)/2)/3. The theorem therefore settles the conjecture of Section 6 of arXiv:2610.22142 for every order $n \ge 30000001$, for both parities and every minimum proper coloring.
The lower bound is Theorem 3.4 of arXiv:2610.22142, formalized as wild_number_complete_graph_min_proper_coloring_ge. The new part is the matching upper bound at every large order. Before this, the upper bound was known for $3 \le n \le 12$ (Theorem 3.5 of the paper; the case $n = 3$ is wild_number_complete_three_min_proper_coloring_eq) and for the single order $n = 279$.
theorem wild_number_complete_graph_large_eq (n k : ℕ) (hn : 30000001 ≤ n)
(hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k)
(c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) :
simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 4*((n+1)/2)/34. Proof
The lower bound is wild_number_complete_graph_min_proper_coloring_ge, so it remains to show $\operatorname{wld}_c(K_n) \le \lfloor 4\lceil n/2\rceil/3 \rfloor$. The proof combines three lemmas.
Lemma 1 (simple_graph_wild_number_le_of_block_cut_condition). If an edge coloring $\gamma$ of $K_n$, with $n > 0$, satisfies the block cut condition for a block partition $p$ into $q$ blocks with roots $r$, then $\operatorname{wld}_\gamma(K_n) \le n - q$.
Proof. Take $W = \{\, u\,r(p(u)) : u \ne r(p(u)) \,\}$, the stars joining each vertex to the root of its block. Then $|W| = n - q$ and each block is connected inside $W$. Fix a color. If the subgraph formed by that color and $W$ were disconnected, some component would be a union of blocks forming a nonempty proper set $S$ of blocks, and no edge of the color would cross from $S$ to its complement, contradicting the cut condition.
Lemma 2 (wild_partition_of_resource_bounds). Let $c$ be a proper coloring of $K_n$ with $n$ colors and let $b$ be a block map into $q$ blocks with roots. Suppose that, for every position $x$, the total weight of the seal events whose domain $\operatorname{pos}(T)$ contains $x$ is at most $1/50$, and that, for every vertex $w$, the total weight of the seal events whose image contains $w$ is at most $1/50$. Then there is a block partition into $q$ rooted blocks for which $c$ satisfies the block cut condition.
Proof. Call two seal events neighbours when their domains or their images meet. The lopsided local lemma for random permutations shows that some permutation $\sigma$ realizes no seal event, provided each event $E$ with domain size $d$ satisfies $$\frac{1}{(n)_d} \le \operatorname{wt}_n(d) \prod_{E' \text{ neighbour of } E} \bigl(1 - \operatorname{wt}_n(d')\bigr).$$ The neighbours of $E$ are covered by $2d$ families, one through each of its $d$ domain positions and one through each of its $d$ image vertices, and each family has total weight at most $1/50$. Hence the product is at least $(49/50)^{2d} \ge (20/21)^d$, which is exactly the inequality required. Now relabel the vertices by $\sigma$, so that vertex $v$ goes to block $b(\sigma^{-1}(v))$. Let $S$ be a nonempty proper set of blocks and let $i$ be a color. Replacing $S$ by its complement if necessary, we may assume $|S| \le \lfloor q/2 \rfloor$; the complement of a set closed under the matching $M_i$ is again closed. If no edge of color $i$ crossed $S$, the vertex set of $S$ would be closed under color $i$, and $\sigma$ would realize the corresponding seal event. So every color crosses every nontrivial cut.
Lemma 3 (wild_partition_large_order_resource_bounds). Let $n$ be odd with $3q \le n \le 3q + 2$ and $q \ge 10^7$. Let $c$ be a proper $n$-coloring of $K_n$, so that each color $i$ misses exactly one vertex $v_i$. Let $b$ be a block map such that every union of $h$ blocks has between $3h$ and $3h + (n - 3q)$ vertices. Then both families of sums in Lemma 2 are at most $1/50$.
Proof. Fix $h$ and a domain of size $k$, where $3h \le k \le 3h + 2$. A vertex set $U$ of size $k$ closed under color $i$ consists of $\lfloor k/2 \rfloor$ edges of $M_i$, together with $v_i$ when $k$ is odd, so there are at most $\binom{\lfloor n/2 \rfloor}{\lfloor k/2 \rfloor}$ choices of $U$ and $k!$ injections onto each. Since $k!/(n)_k = 1/\binom{n}{k}$, the events of one color $i$ and one block set $T$ weigh at most $$P(n,k) = \frac{\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}}{\binom{n}{k}} \left(\frac{21}{20}\right)^{k}.$$ Through a fixed position there are $n$ colors and $\binom{q-1}{h-1}$ sets $T$ of $h$ blocks containing its block, and $n \binom{q-1}{h-1} \le 5q\binom{q-1}{h-1} = 5h\binom{q}{h}$. Through a fixed vertex, the closed sets of size $k$ containing it number $k\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}$ in total over all colors, with $k \le 3h + 2 \le 5h$, and there are $\binom{q}{h}$ sets $T$; this gives the same quantity. So in both cases the contribution of $h$ is at most $5h\binom{q}{h}P(n,k)$, and Lean shows $$5h\binom{q}{h}P(n,k) \le \frac{1}{20000}\, h^2 \left(\frac{5}{6}\right)^h .$$ For $h = 1$ this is a direct estimate with $3 \le k \le 5$. For $h \ge 2$ it follows from four facts: $\binom{q}{h}^3 \le \binom{n}{k}$ and $\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}^2 \le \binom{n}{k}$ (both from Vandermonde's identity), $\binom{q}{h} \ge q(q-1)2^{h-2}/(h(h-1))$, and $(21/20)^6 \le 2(5/6)^2$. Together these give $(5h\binom{q}{h}P(n,k))^2 \le C\,h^4(5/6)^{2h}/(q(q-1))$ for a fixed constant $C$, which is small enough once $q \ge 10^7$. Finally $\sum_{h \ge 0} h^2 (5/6)^h \le 330$, which Lean proves through the identity $\sum_{h<N} h^2(5/6)^h + (6N^2 + 60N + 330)(5/6)^N = 330$. Each total is therefore at most $330/20000 < 1/50$.
Proof of the theorem, odd $n$. Here $k = n$, and each color misses exactly one vertex, which gives a bijection between colors and missing vertices. Write $n = 3q + a$ with $a \in \{0,1,2\}$, so $q \ge 10^7$. Positions $3j, 3j+1, 3j+2$ form block $j$, and the $a$ leftover positions are added to blocks $0, \dots, a-1$. Unions of $h$ blocks then have between $3h$ and $3h + a$ vertices. Lemma 3 gives the bounds required by Lemma 2, Lemma 2 gives a partition satisfying the cut condition, and Lemma 1 gives $\operatorname{wld}_c(K_n) \le n - q = 2q + a$. Since $n$ is odd, $q$ is odd when $a \in \{0, 2\}$ and even when $a = 1$, and in each case $\lfloor 4\lceil n/2\rceil/3 \rfloor = 2q + a$.
Proof of the theorem, even $n$. Write $n = m + 1$ with $m$ odd; then $k = m$. Each color class of $c$ is a perfect matching of $K_n$, so restricting $c$ to the first $m$ vertices gives a proper $m$-coloring of $K_m$ in which every color misses exactly one vertex. Write $m = 3q + a$. The odd case provides a partition of $K_m$ into $q$ rooted blocks with the cut property. Make the last vertex a block of its own, giving $q + 1$ blocks of $K_n$. A nontrivial cut that splits the blocks of $K_m$ is crossed by an edge of $K_m$ of each color. Otherwise one side is exactly the new block, and it is crossed by the edge of the given color at the new vertex. Lemma 1 then gives $\operatorname{wld}_c(K_n) \le n - (q+1) = m - q = 2q + a$. This is the reduction of Section 3.3.3 of arXiv:2610.22142. It remains to check that $2q + a = \lfloor 4\lceil n/2\rceil/3 \rfloor$ with $n = 3q + a + 1$:
- $a = 0$: $q = 2j+1$ is odd, $\lceil n/2 \rceil = 3j + 2$, and $\lfloor 4(3j+2)/3 \rfloor = 4j + 2 = 2q$.
- $a = 1$: $q = 2j$ is even, $\lceil n/2 \rceil = 3j + 1$, and $\lfloor 4(3j+1)/3 \rfloor = 4j + 1 = 2q + 1$.
- $a = 2$: $q = 2j+1$ is odd, $\lceil n/2 \rceil = 3j + 3$, and $\lfloor 4(3j+3)/3 \rfloor = 4j + 4 = 2q + 2$.
In both parities the upper bound meets the lower bound, which proves the equality.
5. Discussion
The theorem settles the conjecture of arXiv:2610.22142 for every $n \ge 30000001$. The paper had already reduced the upper bound to the existence of seal-free block partitions and constructed them by hand for small orders. The contribution here is a uniform existence argument: the local lemma for random permutations, together with the observation that a set closed under a near-perfect matching is determined by $\lfloor k/2 \rfloor$ of its edges, which makes potential seals rare.
The finite range $13 \le n \le 30000000$ remains open, except $n = 279$. The threshold was chosen so that the estimates close with room to spare, and it is far from what the method can give. The binomial bounds $\binom{q}{h}^3 \le \binom{n}{k}$ and $\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor}^2 \le \binom{n}{k}$ are crude for small $h$. Summing the weights exactly for a given $n$ instead of using the bound $(1/20000)h^2(5/6)^h$ could lower the threshold, and a computation of exact weight sums, or explicit constructions as in the paper, could cover the orders that remain.
The paper also studies complete bipartite graphs. Whether a random block placement argument of the same kind gives the matching upper bounds there is a natural next question.
Why it is research-level
- Proves the Section 6 conjecture of arXiv:2610.22142 for every n>=30000001 and every minimum proper edge coloring; before, equality was known only for n<=12 and n=279
Lean declarations
- 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…
- 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⌋.
- wild_number_complete_three_min_proper_coloring_eqFor every minimum proper edge colouring of K_3, the wild number is 2 = ⌊4⌈3/2⌉/3⌋: the case n = 3 of the conjecture in Sec. 6.
- 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…
- wild_partition_of_resource_boundsLet n>0 and let a proper coloring of K_n use the color set Fin n. Fix a partition map b from the vertices onto q blocks, with a specified…
- wild_partition_large_order_resource_boundsSuppose n is odd, q>=10000000, 3q<=n<=3q+2, and a proper n-coloring of K_n has a bijection between colors and their unique missing…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2610.22142 — Wild number for spanning trees in complete and complete bipartite graphs
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.