finset_three_color_busiest_recolor
Given three colors and a finite set excluding a distinguished point, recolor only that point so that at least one third of the set has its new color.
Statement
theorem finset_three_color_busiest_recolor (α : Type) [Fintype α] [DecidableEq α] (col : α → Fin 3) (x : α) (M : Finset α) (hx : x ∉ M) : ∃ col' : α → Fin 3, (∀ v, v ≠ x → col' v = col v) ∧ M.card ≤ 3 * (M.filter fun v => col' v = col' x).card
- Source
- Pigeonhole step in the exceptional-vertex reduction for OP-110.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- digraph_125_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 125 vertices with dominated arcs and a cycle in every in-neighborhood contains four…
The proof, explained
The proof uses the pigeonhole principle: partitioning the set M into three color classes according to col, the sum of their sizes equals |M|, so at least one color class S(i) must satisfy |M| ≤ 3 * |S(i)|. Recoloring x with this majority color i while preserving all other colors ensures that the subset of M matching x's new color is precisely S(i) (since x ∉ M). Therefore, at least one third of M shares the new color assigned to x.
Define S(i) for each color i ∈ {0, 1, 2} as the set of elements in M colored i.
Working classically, we partition the finite set M by color, defining S(i) = {v ∈ M | col(v) = i} for each color i ∈ Fin 3.
classical let S : Fin 3 → Finset α := fun i => M.filter fun v => col v = i
The cardinality of M is the sum of the cardinalities of its three color classes: |M| = |S(0)| + |S(1)| + |S(2)|.
By Finset.card_eq_sum_card_fiberwise, partitioning M along the fibers of the coloring col expresses |M| as the sum of fiber cardinalities over Finset.univ. Applying Fin.sum_univ_three expands this sum over Fin 3 into the three terms |S(0)| + |S(1)| + |S(2)|.
uses
Finset.card_eq_sum_card_fiberwise,Fin.sum_univ_threehave hsum : M.card = (S 0).card+(S 1).card+(S 2).card := by have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := M) (t := (Finset.univ : Finset (Fin 3))) (by simp) simp only [Fin.sum_univ_three] at h change M.card = (S 0).card + (S 1).card + (S 2).card at h exact h
There is at least one color i ∈ {0, 1, 2} such that |M| ≤ 3 * |S(i)|.
By contradiction, suppose no such color exists. Then 3 * |S(i)| < |M| for each of i = 0, 1, 2. Summing these three strict inequalities gives 3 * (|S(0)| + |S(1)| + |S(2)|) < 3 * |M|, which contradicts |M| = |S(0)| + |S(1)| + |S(2)|; linear integer arithmetic (omega) derives False from this system.
have hi : ∃ i : Fin 3, M.card ≤ 3 * (S i).card := by by_contra hn have h0 : 3*(S 0).card < M.card := by by_contra h; exact hn ⟨0, by omega⟩ have h1 : 3*(S 1).card < M.card := by by_contra h; exact hn ⟨1, by omega⟩ have h2 : 3*(S 2).card < M.card := by by_contra h; exact hn ⟨2, by omega⟩ omega
Choose such a majority color i and define a new coloring col' that changes only the color of x to i.
We unpack the witness i satisfying |M| ≤ 3 * |S(i)| and define col' to map x to i and every other element v to col(v). The goal splits into showing that col' agrees with col away from x, and that |M| ≤ 3 * |{v ∈ M | col'(v) = col'(x)}|.
obtain ⟨i,hi⟩ := hi let col' : α → Fin 3 := fun v => if v = x then i else col v refine ⟨col', ?_, ?_⟩
For any vertex v ≠ x, the new coloring satisfies col'(v) = col(v).
Since v ≠ x, the conditional definition of col'(v) immediately simplifies to col(v).
· intro v hv simp [col',hv]
The elements in M that share x's new color under col' are precisely the elements of S(i).
We verify the set equality by extensionality. For any v ∈ M, the hypothesis x ∉ M ensures v ≠ x, so col'(v) = col(v); since col'(x) = i, the condition col'(v) = col'(x) is equivalent to col(v) = i, placing v in S(i). If v ∉ M, it belongs to neither set.
· have heq : (M.filter fun v => col' v = col' x) = S i := by ext v by_cases hv : v ∈ M · have hvx : v ≠ x := by intro h; subst v; exact hx hv simp [S,col',hv,hvx] · simp [S,hv]
At least one third of the elements in M have the color col'(x).
Rewriting the filtered set {v ∈ M | col'(v) = col'(x)} as S(i) reduces the goal to |M| ≤ 3 * |S(i)|, which holds by our choice of i.
rw [heq] exact hi
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set s mapped by f into t is the sum over all elements b of t of the cardinalities of the fibers {a ∈ s | f a = b}.
Fin.sum_univ_three- The sum of a function f over all elements of Fin 3 equals f(0) + f(1) + f(2).
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.
theorem finset_three_color_busiest_recolor (α : Type) [Fintype α] [DecidableEq α] (col : α → Fin 3) (x : α) (M : Finset α) (hx : x ∉ M) : ∃ col' : α → Fin 3, (∀ v, v ≠ x → col' v = col v) ∧ M.card ≤ 3 * (M.filter fun v => col' v = col' x).card := by classical let S : Fin 3 → Finset α := fun i => M.filter fun v => col v = i have hsum : M.card = (S 0).card+(S 1).card+(S 2).card := by have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := M) (t := (Finset.univ : Finset (Fin 3))) (by simp) simp only [Fin.sum_univ_three] at h change M.card = (S 0).card + (S 1).card + (S 2).card at h exact h have hi : ∃ i : Fin 3, M.card ≤ 3 * (S i).card := by by_contra hn have h0 : 3*(S 0).card < M.card := by by_contra h; exact hn ⟨0, by omega⟩ have h1 : 3*(S 1).card < M.card := by by_contra h; exact hn ⟨1, by omega⟩ have h2 : 3*(S 2).card < M.card := by by_contra h; exact hn ⟨2, by omega⟩ omega obtain ⟨i,hi⟩ := hi let col' : α → Fin 3 := fun v => if v = x then i else col v refine ⟨col', ?_, ?_⟩ · intro v hv simp [col',hv] · have heq : (M.filter fun v => col' v = col' x) = S i := by ext v by_cases hv : v ∈ M · have hvx : v ≠ x := by intro h; subst v; exact hx hv simp [S,col',hv,hvx] · simp [S,hv] rw [heq] exact hi