quadripartite_max_wild_number_eq_of_bounds
The maximum wild number equals 2n + 1 as soon as every proper 3n-edge-colouring of K_{n,n,n,n} has wild number at most 2n + 1 and some such colouring has wild number exactly 2n + 1.
Statement
theorem quadripartite_max_wild_number_eq_of_bounds (n : ℕ)
(hU : ∀ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),
simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c ≤ 2 * n + 1)
(hE : ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),
simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = 2 * n + 1) :
quadripartite_max_wild_number n = 2 * n + 1- Source
- step towards quadripartite_minimum_coloring_max_wild_number_eq
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- quadripartite_max_wild_numberThe maximum wild number of the complete equipartite graph K_{n,n,n,n} over all proper edge colorings using exactly 3n colors.
- 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 maximum wild number is defined as the supremum of the set S of wild numbers achieved by proper (3n)-edge-colourings of K_{n,n,n,n}. For a bounded subset of ℕ, this supremum is the least upper bound. The proof checks that 2n + 1 is an upper bound via the universal bound hypothesis, and that 2n + 1 belongs to S via the existence hypothesis, so by antisymmetry the least upper bound is exactly 2n + 1.
The goal is to show that the supremum of the set S of all wild numbers attained by proper (3n)-edge-colourings of K_{n,n,n,n} is 2n + 1.
Unfold the definition of quadripartite_max_wild_number and introduce the abbreviation S for the set of wild numbers attained by proper (3n)-edge-colourings of the complete equipartite graph K_{n,n,n,n}.
classical unfold quadripartite_max_wild_number set S := {k : ℕ | ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)), simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = k}
The set S is bounded above by 2n + 1.
The hypothesis hU states that every proper (3n)-edge-colouring has wild number at most 2n + 1. Thus every element a ∈ S satisfies a ≤ 2n + 1, giving an upper bound N = 2n + 1.
have hbd : ∃ N, ∀ a ∈ S, a ≤ N := by use 2 * n + 1 rintro a ⟨c, rfl⟩ exact hU c
The supremum of S is the least upper bound Nat.find hbd.
Using Nat.sSup_def with the upper bound certificate hbd, the supremum of S in ℕ is by definition the smallest natural number that bounds S from above.
uses
Nat.sSup_defrw [Nat.sSup_def hbd]It suffices to show that Nat.find hbd ≤ 2n + 1 and 2n + 1 ≤ Nat.find hbd.
By antisymmetry of the partial order on ℕ (le_antisymm), equality reduces to the two non-strict inequalities.
uses
le_antisymmapply le_antisymmNat.find hbd ≤ 2n + 1.
By Nat.find_min', the least upper bound is bounded above by any valid upper bound. Since 2n + 1 is an upper bound for S (by hU), Nat.find hbd ≤ 2n + 1.
uses
Nat.find_min'· apply Nat.find_min' rintro a ⟨c, rfl⟩ exact hU c
2n + 1 ≤ Nat.find hbd.
By hypothesis hE, there exists a colouring c with wild number exactly 2n + 1, so 2n + 1 ∈ S. Because Nat.find hbd is an upper bound for every element of S (Nat.find_spec), 2n + 1 ≤ Nat.find hbd.
uses
Nat.find_spec· obtain ⟨c, hc⟩ := hE have hmem : 2 * n + 1 ∈ S := ⟨c, hc⟩ exact Nat.find_spec hbd (2 * n + 1) hmem
Nat.sSup_def- for a set of natural numbers with an upper bound, its supremum is defined as the least upper bound, given by the minimal natural number satisfying the upper-bound predicate
le_antisymm- if a ≤ b and b ≤ a in a partial order, then a = b
Nat.find_min'- if a predicate on ℕ holds for m, then the minimal natural number satisfying the predicate is at most m
Nat.find_spec- the minimal natural number found by Nat.find satisfies the defining predicate
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.
/-- The maximum wild number is 2n + 1 once the universal upper bound and one attaining colouring are available. -/theorem quadripartite_max_wild_number_eq_of_bounds (n : ℕ) (hU : ∀ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)), simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c ≤ 2 * n + 1) (hE : ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)), simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = 2 * n + 1) : quadripartite_max_wild_number n = 2 * n + 1 := by classical unfold quadripartite_max_wild_number set S := {k : ℕ | ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)), simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = k} have hbd : ∃ N, ∀ a ∈ S, a ≤ N := by use 2 * n + 1 rintro a ⟨c, rfl⟩ exact hU c rw [Nat.sSup_def hbd] apply le_antisymm · apply Nat.find_min' rintro a ⟨c, rfl⟩ exact hU c · obtain ⟨c, hc⟩ := hE have hmem : 2 * n + 1 ∈ S := ⟨c, hc⟩ exact Nat.find_spec hbd (2 * n + 1) hmem