wild_closed_cut_of_additive_translation
Let a proper complete-graph edge coloring have an injective labeling of its vertices and colors in an exponent-two commutative group, with each edge color label equal to the sum of its endpoint labels. If the labels of a vertex set are stable under translation by one color label, that vertex set is closed under edges of that color.
Statement
theorem wild_closed_cut_of_additive_translation {G : Type*} [AddCommGroup G] [DecidableEq G] {n : ℕ} (h2 : ∀ a : G, a + a = 0) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (lab : Fin n → G) (hinj : Function.Injective lab) (hcol : ∀ u v (h : u ≠ v), lab (c ⟨s(u,v), wild_kn_mem h⟩) = lab u + lab v) (i : Fin n) (U : Finset (Fin n)) (htrans : ∀ u ∈ U, lab u + lab i ∈ U.image lab) : w279_closed c i U
- 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 2
- 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…
- 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_binary_leaf_signature_collision_closedFor a properly colored complete graph whose vertex/color labels bijectively enumerate the nonzero elements of an exponent-two commutative…
The proof, explained
To prove that U is closed under edges of color i, consider any vertex u ∈ U connected to a vertex v by an edge of color i. In an exponent-two group, the endpoint-sum coloring condition lab(u) + lab(v) = lab(i) can be rearranged to lab(v) = lab(u) + lab(i). Since U is stable under translation by lab(i), this sum is the label of some vertex w ∈ U, and injectivity of the labeling forces v = w ∈ U.
To show that U is closed under edges of color i, let u ∈ U and let v be an adjacent vertex such that the edge between u and v has color i; it suffices to show that v ∈ U.
Unfolding the definition of a closed vertex set (w279_closed c i U), we assume u ∈ U, a vertex v with u ≠ v, and that the edge {u, v} has color i. The goal is to prove that v ∈ U.
intro u hu v huv hcThe label of vertex v equals lab(u) + lab(i).
Since every element in G has order two (h2: a + a = 0), we can express lab(v) as 0 + lab(v) = (lab(u) + lab(u)) + lab(v) = lab(u) + (lab(u) + lab(v)). By the coloring assumption hcol, the sum lab(u) + lab(v) is the label of the color of edge {u, v}, which equals lab(i). Hence lab(v) = lab(u) + lab(i).
uses
zero_addhave hv : lab v = lab u + lab i := by calc _ = (lab u + lab u) + lab v := by rw [h2, zero_add] _ = lab u + (lab u + lab v) := by abel _ = lab u + lab i := by rw [← hcol u v huv, hc]
The vertex v belongs to U.
By the translation stability hypothesis htrans, lab(u) + lab(i) belongs to the image of U under lab. Unpacking this finset image membership gives a vertex w ∈ U with lab(w) = lab(u) + lab(i). Since lab(w) = lab(v) and the labeling is injective (hinj), we have w = v, which implies v ∈ U.
uses
mem_image.mpobtain ⟨w, hw, hweq⟩ := mem_image.mp (htrans u hu) have : w = v := hinj (hweq.trans hv.symm) simpa only [this] using hw
zero_add- in any additive structure with zero, adding zero on the left leaves the element unchanged: 0 + a = a
mem_image.mp- an element b is in the image of a finite set s under f if and only if b = f(a) for some a ∈ 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 Finsetset_option maxHeartbeats 2500000theorem wild_closed_cut_of_additive_translation {G : Type*} [AddCommGroup G] [DecidableEq G] {n : ℕ} (h2 : ∀ a : G, a + a = 0) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (lab : Fin n → G) (hinj : Function.Injective lab) (hcol : ∀ u v (h : u ≠ v), lab (c ⟨s(u,v), wild_kn_mem h⟩) = lab u + lab v) (i : Fin n) (U : Finset (Fin n)) (htrans : ∀ u ∈ U, lab u + lab i ∈ U.image lab) : w279_closed c i U := by intro u hu v huv hc have hv : lab v = lab u + lab i := by calc _ = (lab u + lab u) + lab v := by rw [h2, zero_add] _ = lab u + (lab u + lab v) := by abel _ = lab u + lab i := by rw [← hcol u v huv, hc] obtain ⟨w, hw, hweq⟩ := mem_image.mp (htrans u hu) have : w = v := hinj (hweq.trans hv.symm) simpa only [this] using hw