wild_no_closed_union_of_blocks
If every used color crosses every nonempty proper cut of the block labels under p, then no nonempty proper vertex set that is a union of p-fibers is closed under a used color.
Statement
theorem wild_no_closed_union_of_blocks {n k q : ℕ}
(c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (p : Fin n → Fin q)
(hcut : ∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin q)),
S.Nonempty → S ≠ Finset.univ →
∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e)
(e : (⊤ : SimpleGraph (Fin n)).edgeSet) (U : Finset (Fin n))
(hU : U.Nonempty) (hproper : U ≠ Finset.univ)
(hsat : ∀ u ∈ U, ∀ v, p v = p u → v ∈ U) : ¬w279_closed c (c e) U- Source
- Certificate-soundness and finite averaging helpers for the OP-306 campaign on arXiv:2610.22142, Sections 3.3.1 and 3.3.2. The thirteen-vertex equivalence is a reduction, not a proof of the conjectured equality; the moment criterion supplies no unproved universal numerical hypothesis.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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…
- complete_graph_odd_line_graph_chromatic_number_eqThe edge chromatic number of an odd complete graph on at least three vertices is its number of vertices.
- 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_complete_thirteen_partition_templateFor every partition p of thirteen vertices into four labeled blocks of size at least three, there are vertex and block-label permutations…
- wild_complete_thirteen_one_swap_repair_obstructionThere exists a minimum proper 13-coloring of K_13, normalized so that color i misses vertex i, with this property. The fixed partition…
- 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_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⌋.
- Used by 1
- wild_number_complete_thirteen_eq_iff_permuted_cutsFor every proper 13-coloring of K_13, its wild number is nine if and only if some permutation of the canonical 3+3+3+4 vertex partition…
The proof, explained
The proof argues by contradiction: suppose a nonempty proper vertex set U, which is a union of fibers of p, is closed under the color of edge e. Its image S = p(U) in the block labels is nonempty, and it must be a proper subset because otherwise fiber-saturation would force U to contain every vertex. By hypothesis, every nonempty proper cut of block labels is crossed by an edge of color c(e), yielding an edge uv with p(u) ∈ S and p(v) ∉ S. By fiber-saturation, u must be in U; the closure of U then forces v into U, which contradicts p(v) ∉ S.
Assume for contradiction that U is closed under color c(e), and define S to be the image p(U), which is nonempty.
We assume for contradiction (hcl) that U is closed under monochromatic edges of color c(e). We define S to be the image of U under the block projection p. Since U is nonempty (hU), its image S is also nonempty.
classical intro hcl let S : Finset (Fin q) := U.image p have hS : S.Nonempty := hU.image p
S is a proper subset of the block labels (S ≠ Finset.univ).
Suppose for contradiction that S = Finset.univ. To show this contradicts U ≠ Finset.univ (hproper), by Finset.eq_univ_of_forall it suffices to show every vertex v belongs to U. For any vertex v, its block p(v) belongs to S = Finset.univ by Finset.mem_univ. By definition of the image (Finset.mem_image.1), there is some u ∈ U such that p(u) = p(v). Since U is a union of fibers of p (hsat), p(v) = p(u) implies v ∈ U. Hence U would be the entire vertex set, contradicting hproper.
uses
Finset.eq_univ_of_forall,Finset.mem_univ,Finset.mem_image.1have hSp : S ≠ Finset.univ := by intro hh apply hproper apply Finset.eq_univ_of_forall intro v have hv : p v ∈ S := hh ▸ Finset.mem_univ _ obtain ⟨u,hu,hp⟩ := Finset.mem_image.1 hv exact hsat u hu v hp.symm
There is an edge uv of color c(e) crossing the cut between S and its complement.
Because S is a nonempty proper subset of block labels, the cut-crossing hypothesis hcut applied to edge e and set S provides two distinct vertices u and v such that p(u) ∈ S, p(v) ∉ S, and the edge uv has color c(e).
obtain ⟨u,v,huv,hu,hv,hc⟩ := hcut e S hS hSpBoth u and v must belong to U, contradicting p(v) ∉ S.
Since p(u) ∈ S = p(U), there is some x ∈ U with p(x) = p(u) by Finset.mem_image.1. Because U is a union of fibers (hsat), u belongs to U. By the assumed closure of U under color c(e) (hcl), the edge uv of color c(e) forces v to belong to U as well. But if v ∈ U, then p(v) ∈ p(U) = S by Finset.mem_image_of_mem, which directly contradicts p(v) ∉ S.
uses
Finset.mem_image.1,Finset.mem_image_of_memobtain ⟨x,hx,hpx⟩ := Finset.mem_image.1 hu have huU := hsat x hx u hpx.symm have hvU := hcl u huU v huv hc exact hv (Finset.mem_image_of_mem p hvU)
Finset.eq_univ_of_forall- A finite set s of a finite type contains all elements if and only if it is equal to the universal set.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.mem_image.1- If y belongs to the image f(s), then there exists some element x in s such that f(x) = y.
Finset.mem_image_of_mem- If an element a belongs to s, then f(a) belongs to the image f(s).
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 scoped BigOperators Classicalset_option maxHeartbeats 1600000set_option maxRecDepth 100000theorem wild_no_closed_union_of_blocks {n k q : ℕ} (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (p : Fin n → Fin q) (hcut : ∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin q)), S.Nonempty → S ≠ Finset.univ → ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e) (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (U : Finset (Fin n)) (hU : U.Nonempty) (hproper : U ≠ Finset.univ) (hsat : ∀ u ∈ U, ∀ v, p v = p u → v ∈ U) : ¬w279_closed c (c e) U := by classical intro hcl let S : Finset (Fin q) := U.image p have hS : S.Nonempty := hU.image p have hSp : S ≠ Finset.univ := by intro hh apply hproper apply Finset.eq_univ_of_forall intro v have hv : p v ∈ S := hh ▸ Finset.mem_univ _ obtain ⟨u,hu,hp⟩ := Finset.mem_image.1 hv exact hsat u hu v hp.symm obtain ⟨u,v,huv,hu,hv,hc⟩ := hcut e S hS hSp obtain ⟨x,hx,hpx⟩ := Finset.mem_image.1 hu have huU := hsat x hx u hpx.symm have hvU := hcl u huU v huv hc exact hv (Finset.mem_image_of_mem p hvU)