wild_rainbow_equal_blocks_closed_matching_crosses
In a properly colored complete graph with one specified missing vertex for each color, let two disjoint equally sized blocks have no common internal color except i0. If a different color i closes their union, every color-i partner of a vertex in the first block belongs to the second block.
Statement
theorem wild_rainbow_equal_blocks_closed_matching_crosses
{n k : ℕ}
(c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
(m : Fin k → Fin n)
(hm : ∀ i v, (∀ w (h : v ≠ w), c ⟨s(v,w),wild_kn_mem h⟩ ≠ i) ↔ v = m i)
(A B : Finset (Fin n)) (hdis : Disjoint A B) (hcard : A.card = B.card)
(i0 i : Fin k) (hne : i ≠ i0)
(hsep : ∀ a ∈ A, ∀ a' ∈ A, ∀ ha : a ≠ a',
∀ b ∈ B, ∀ b' ∈ B, ∀ hb : b ≠ b',
c ⟨s(a,a'),wild_kn_mem ha⟩ = c ⟨s(b,b'),wild_kn_mem hb⟩ →
c ⟨s(a,a'),wild_kn_mem ha⟩ = i0)
(hclosed : w279_closed c i (A ∪ B)) :
∀ a ∈ A, w279_pc c i a ∈ B- Source
- IN-338 structural/repair helpers for OP-306, the prescribed-coloring conjecture in arXiv:2610.22142 Sections3.3.2 and6. Exact matching-involution balance and the method obstruction computed in experiment8464. These are certificate/method lemmas, not new wild-number bounds or research advances.
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- involution_equal_blocks_internal_cardIf an involution preserves the union of two disjoint finite blocks of equal cardinality, the number of vertices paired internally in the…
- 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⌋.
The proof, explained
The theorem is proved by contradiction. First, the missing vertex m(i) of color i cannot lie in A ∪ B, because |A ∪ B| = 2|A| is even, whereas a closed set containing m(i) must have odd cardinality. Thus the color-i partner operation p is a fixed-point-free involution on A ∪ B, which by an equicardinal block counting lemma implies that the number of internal color-i pairs in A equals the number in B. If some a ∈ A had its partner outside B, it would fall in A, forcing an internal color-i pair in B as well; but by hypothesis, the only internal color shared by A and B is i0, contradicting i ≠ i0.
Enable classical reasoning and define p as the color-i partner function.
We work classically and define p(v) = w279_pc c i v, which assigns to each vertex v its partner along the incident edge of color i.
classical let p := w279_pc c iThe missing vertex m(i) of color i does not belong to A ∪ B.
Suppose for contradiction that m(i) ∈ A ∪ B. Since A and B are disjoint with equal cardinality, |A ∪ B| = |A| + |B| = 2|A| is even. However, because A ∪ B is closed under color i, the formula from `w279_card_closed` implies |A ∪ B| = 2k + 1 (since m(i) ∈ A ∪ B gives 1 via `if_pos`), which is odd. Linear integer arithmetic (`omega`) detects the impossibility of an even integer equaling an odd integer and derives False.
uses
w279_card_closed,if_pos,card_union_of_disjointhave hmiss : m i ∉ A ∪ B := by intro hmi have hh := w279_card_closed c m hm i (A ∪ B) hclosed rw [if_pos hmi, card_union_of_disjoint hdis] at hh omega
No vertex in A ∪ B equals the missing vertex m(i).
If some vertex v ∈ A ∪ B satisfied v = m(i), then m(i) would belong to A ∪ B, directly contradicting the previous step.
have hvne : ∀ v ∈ A ∪ B, v ≠ m i := by intro v hv he exact hmiss (he ▸ hv)
The partner map p preserves A ∪ B.
By `w279_closed_iff`, a set is closed under color i if and only if every element different from m(i) has its color-i partner in the set. Since A ∪ B is closed and contains no vertex equal to m(i), p(v) ∈ A ∪ B for every v ∈ A ∪ B.
uses
w279_closed_iffhave hstable : ∀ v ∈ A ∪ B, p v ∈ A ∪ B := by intro v hv exact (w279_closed_iff c m hm i (A ∪ B)).mp hclosed v hv (hvne v hv)
On A ∪ B, the map p is an involution: p(p(v)) = v for all v ∈ A ∪ B.
Because no vertex v in A ∪ B is the missing vertex m(i), each such vertex is paired along a color-i edge with p(v), and iterating the partner map returns the original vertex v by `w279_pc_pc`.
uses
w279_pc_pchave hinv : ∀ v ∈ A ∪ B, p (p v) = v := by intro v hv exact w279_pc_pc c m hm i v (hvne v hv)
The number of vertices in A whose color-i partner lies in A equals the number of vertices in B whose color-i partner lies in B.
Since A and B are disjoint sets of equal size and p is an involution on A ∪ B preserving A ∪ B, the lemma `involution_equal_blocks_internal_card` applies directly to equate the counts of internal pairs in A and in B.
uses
involution_equal_blocks_internal_cardhave heq := involution_equal_blocks_internal_card p A B hdis hcard hstable hinvIf some vertex a ∈ A had its partner outside B (so p(a) ∈ A), then there would also exist a vertex in B whose partner is in B.
Assume for contradiction that p(a) ∉ B for some a ∈ A. Since p(a) ∈ A ∪ B, this forces p(a) ∈ A. Thus the set of vertices in A mapped into A contains a, so its cardinality is strictly positive. By the equality of internal counts between A and B, the set of vertices in B mapped into B also has strictly positive cardinality (`omega`).
uses
mem_union,mem_union_left,card_pos,mem_filterintro a ha by_contra hpB have hpA : p a ∈ A := (mem_union.mp (hstable a (mem_union_left B ha))).resolve_right hpB have hposA : 0 < (A.filter fun v => p v ∈ A).card := card_pos.mpr ⟨a,mem_filter.mpr ⟨ha,hpA⟩⟩ have hposB : 0 < (B.filter fun v => p v ∈ B).card := by omega
The existence of internal color-i pairs in both A and B contradicts i ≠ i0, completing the proof.
Because the set of internal partners in B is nonempty, choose a vertex b ∈ B with p(b) ∈ B. By `w279_pc_spec`, the edge between a and p(a) has color i, and the edge between b and p(b) has color i. Both are internal edges in A and B respectively. By the block separation hypothesis `hsep`, any color shared by an internal edge in A and an internal edge in B must be i0, so i = i0. This contradicts the hypothesis i ≠ i0 (`hne`).
uses
card_pos,mem_filter,w279_pc_spec,mem_union_left,mem_union_rightobtain ⟨b,hb⟩ := card_pos.mp hposB obtain ⟨hbB,hpB'⟩ := mem_filter.mp hb obtain ⟨hane,hac⟩ := w279_pc_spec c m hm i a (hvne a (mem_union_left B ha)) obtain ⟨hbne,hbc⟩ := w279_pc_spec c m hm i b (hvne b (mem_union_right A hbB)) have hci0 := hsep a ha (p a) hpA hane b hbB (p b) hpB' hbne (hac.trans hbc.symm) exact hne (hac.symm.trans hci0)
card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
card_pos- A finite set has cardinality strictly greater than zero if and only if it contains at least one element.
if_pos- If a condition holds, an if-then-else expression evaluates to its 'then' branch.
involution_equal_blocks_internal_card- For any involution on the union of two disjoint sets of equal cardinality that maps the union to itself, the number of elements in the first set mapped into itself equals the number of elements in the second set mapped into itself.
mem_filter- An element belongs to a filtered set {x ∈ s | P x} if and only if it belongs to s and satisfies the predicate P.
mem_union- An element belongs to the union of two sets if and only if it belongs to at least one of them.
mem_union_left- An element belonging to a set s also belongs to s ∪ t.
mem_union_right- An element belonging to a set t also belongs to s ∪ t.
w279_card_closed- For a set U closed under color i, the cardinality of U equals 2k + 1 if the missing vertex m(i) is in U, and 2k if it is not.
w279_closed_iff- A set U is closed under color i if and only if for every u ∈ U with u ≠ m(i), the color-i partner of u also lies in U.
w279_pc_pc- For any vertex v ≠ m(i), applying the color-i partner operation twice returns v.
w279_pc_spec- For any vertex v ≠ m(i), v is distinct from its color-i partner w279_pc c i v, and the edge connecting them has color i.
- The automated tactic `omega` is used in line 23 to derive a contradiction between the parity of |A ∪ B| = 2|A| (even) and the formula 2k + 1 (odd), and in line 38 to deduce 0 < |{v ∈ B | p v ∈ B}| from 0 < |{v ∈ A | p v ∈ A}| and the equality of the two cardinalities.
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_rainbow_equal_blocks_closed_matching_crosses {n k : ℕ} (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (m : Fin k → Fin n) (hm : ∀ i v, (∀ w (h : v ≠ w), c ⟨s(v,w),wild_kn_mem h⟩ ≠ i) ↔ v = m i) (A B : Finset (Fin n)) (hdis : Disjoint A B) (hcard : A.card = B.card) (i0 i : Fin k) (hne : i ≠ i0) (hsep : ∀ a ∈ A, ∀ a' ∈ A, ∀ ha : a ≠ a', ∀ b ∈ B, ∀ b' ∈ B, ∀ hb : b ≠ b', c ⟨s(a,a'),wild_kn_mem ha⟩ = c ⟨s(b,b'),wild_kn_mem hb⟩ → c ⟨s(a,a'),wild_kn_mem ha⟩ = i0) (hclosed : w279_closed c i (A ∪ B)) : ∀ a ∈ A, w279_pc c i a ∈ B := by classical let p := w279_pc c i have hmiss : m i ∉ A ∪ B := by intro hmi have hh := w279_card_closed c m hm i (A ∪ B) hclosed rw [if_pos hmi, card_union_of_disjoint hdis] at hh omega have hvne : ∀ v ∈ A ∪ B, v ≠ m i := by intro v hv he exact hmiss (he ▸ hv) have hstable : ∀ v ∈ A ∪ B, p v ∈ A ∪ B := by intro v hv exact (w279_closed_iff c m hm i (A ∪ B)).mp hclosed v hv (hvne v hv) have hinv : ∀ v ∈ A ∪ B, p (p v) = v := by intro v hv exact w279_pc_pc c m hm i v (hvne v hv) have heq := involution_equal_blocks_internal_card p A B hdis hcard hstable hinv intro a ha by_contra hpB have hpA : p a ∈ A := (mem_union.mp (hstable a (mem_union_left B ha))).resolve_right hpB have hposA : 0 < (A.filter fun v => p v ∈ A).card := card_pos.mpr ⟨a,mem_filter.mpr ⟨ha,hpA⟩⟩ have hposB : 0 < (B.filter fun v => p v ∈ B).card := by omega obtain ⟨b,hb⟩ := card_pos.mp hposB obtain ⟨hbB,hpB'⟩ := mem_filter.mp hb obtain ⟨hane,hac⟩ := w279_pc_spec c m hm i a (hvne a (mem_union_left B ha)) obtain ⟨hbne,hbc⟩ := w279_pc_spec c m hm i b (hvne b (mem_union_right A hbB)) have hci0 := hsep a ha (p a) hpA hane b hbB (p b) hpB' hbne (hac.trans hbc.symm) exact hne (hac.symm.trans hci0)