op861_selector_palette_lower_bound
In any pair of proper standard-list selectors at positive k and threshold r, each selector uses at least k+r distinct colors.
Statement
theorem op861_selector_palette_lower_bound (k r : ℕ) (hk : 1 ≤ k) (f g : {S : Finset (Fin (2*k-1)) // S.card = k} → Fin (2*k-1)) (hf : ∀ S, f S ∈ S.val) (hg : ∀ S, g S ∈ S.val) (hfg : ∀ S T, (S.val ∩ T.val).card ≤ r → f S ≠ g T) : k+r ≤ (Finset.univ.image f).card ∧ k+r ≤ (Finset.univ.image g).card- Source
- A used-palette restriction for the standard-list coloring in arXiv:2610.42094; the case of two size-six palettes at k=6, r=3 is illustrated by experiment 26970.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is established by first proving a one-sided lower bound showing that any valid selector f uses at least k + r colors, and then applying symmetry to obtain the same bound for g. To show |im(f)| ≥ k + r, we assume for contradiction that the palette P = im(f) satisfies |P| = k + s with s + 1 ≤ r. For every (s+1)-subset X ⊆ P, completing X with the complement Pᶜ yields a k-subset S(X) whose selector value f(S(X)) must lie in X ⊆ P. The set A of all such values satisfies |P \ A| ≤ s (hence |A| ≥ k), yet any k-subset T ⊆ A forces an intersection |S(X) ∩ T| = |X ∩ T| ≤ s + 1 ≤ r with f(S(X)) = g(T), contradicting the separation hypothesis.
The palette P = f(univ) of selector f contains at least k colors.
Let P be the image of f. We first show |P| ≥ k. If instead |P| < k, then the complement Pᶜ in the universe of size 2k - 1 would have cardinality at least k (via card_compl and Fintype.card_fin). Choosing a subset t ⊆ Pᶜ of size k via exists_subset_card_eq gives a valid k-set S = t. Since f is a selector, f(S) ∈ S ⊆ Pᶜ, so f(S) ∉ P. But f(S) must belong to P by definition of the image, yielding a contradiction.
uses
card_compl,Fintype.card_fin,exists_subset_card_eq,mem_image_of_mem,mem_univ,mem_complset P := Finset.univ.image f have hk_le : k ≤ P.card := by by_contra! hlt have hcompl : k ≤ Pᶜ.card := by rw [card_compl, Fintype.card_fin] omega obtain ⟨t, ht_sub, ht_card⟩ := exists_subset_card_eq hcompl let S : {S : Finset (Fin (2*k-1)) // S.card = k} := ⟨t, ht_card⟩ have hfS_in_compl : f S ∈ Pᶜ := ht_sub (hf S) have hfS_in_P : f S ∈ P := mem_image_of_mem _ (mem_univ S) rw [mem_compl] at hfS_in_compl exact hfS_in_compl hfS_in_P
Assuming for contradiction that |P| < k + r, setting s = |P| - k gives s + 1 ≤ r and |Pᶜ| = k - 1 - s.
Suppose for contradiction that |P| < k + r. Defining s = |P| - k ≥ 0, we have |P| = k + s, and the contradiction hypothesis immediately implies s + 1 ≤ r. Because P is a subset of the (2k - 1)-element universe, |P| ≤ 2k - 1 (using card_le_card, subset_univ, card_univ, and Fintype.card_fin). Consequently, the complement Pᶜ has cardinality |Pᶜ| = (2k - 1) - (k + s) = k - 1 - s.
uses
card_le_card,subset_univ,card_univ,Fintype.card_fin,card_complby_contra! hlt set s := P.card - k have hPcard : P.card = k + s := by omega have hsr : s + 1 ≤ r := by omega have hPle : P.card ≤ 2 * k - 1 := by have h1 := card_le_card (subset_univ P) rw [card_univ, Fintype.card_fin] at h1 exact h1 have hc : Pᶜ.card = k - 1 - s := by rw [card_compl, Fintype.card_fin, hPcard] omega
For every (s+1)-element subset X ⊆ P, X ∪ Pᶜ is a valid k-set S(X), and the set A of all chosen values f(S(X)) is a subset of P.
For any X ⊆ P with |X| = s + 1, X is disjoint from Pᶜ. By card_union_eq_card_add_card, |X ∪ Pᶜ| = (s + 1) + (k - 1 - s) = k, so S(X) = X ∪ Pᶜ is a valid k-set. We define A to be the set of selector values f(S(X)) across all (s+1)-subsets X of P. Every element of A is f evaluated at some k-set, hence A ⊆ P by mem_image_of_mem and mem_univ.
uses
mem_powersetCard,card_union_eq_card_add_card,mem_image_of_mem,mem_univlet S_of : (X : Finset (Fin (2*k-1))) → X ∈ P.powersetCard (s + 1) → {S : Finset (Fin (2*k-1)) // S.card = k} := fun X hX => have hX' := mem_powersetCard.mp hX have hdisj : Disjoint X Pᶜ := disjoint_compl_right.mono_left hX'.1 ⟨X ∪ Pᶜ, by rw [card_union_eq_card_add_card.2 hdisj, hX'.2, hc]; omega⟩ let A := (P.powersetCard (s + 1)).attach.image (fun ⟨X, hX⟩ => f (S_of X hX)) have hAP : A ⊆ P := by intro a ha simp only [A, mem_image, mem_attach, true_and, Subtype.exists] at ha obtain ⟨X, hX, rfl⟩ := ha exact mem_image_of_mem _ (mem_univ _)
The set difference P \ A has cardinality at most s.
Suppose for contradiction that |P \ A| > s, so |P \ A| ≥ s + 1. By exists_subset_card_eq, choose an (s+1)-element subset X ⊆ P \ A. Since X ⊆ P \ A ⊆ P (using sdiff_subset), X is an (s+1)-subset of P. The selector f picks f(S(X)) ∈ S(X) = X ∪ Pᶜ. Since f(S(X)) ∈ P, it cannot lie in Pᶜ (by mem_compl), so f(S(X)) ∈ X. But X ⊆ P \ A implies f(S(X)) ∉ A, which directly contradicts the fact that f(S(X)) ∈ A by definition of A.
uses
exists_subset_card_eq,sdiff_subset,mem_powersetCard,mem_union,mem_image_of_mem,mem_compl,mem_sdiffhave hdiff : (P \ A).card ≤ s := by by_contra! hgt obtain ⟨X, hX_sub, hX_card⟩ := exists_subset_card_eq hgt have hXP : X ⊆ P := hX_sub.trans sdiff_subset have hX_mem : X ∈ P.powersetCard (s + 1) := by rw [mem_powersetCard] exact ⟨hXP, hX_card⟩ have hf_in_X : f (S_of X hX_mem) ∈ X := by have h1 : f (S_of X hX_mem) ∈ (S_of X hX_mem).val := hf _ rw [mem_union] at h1 cases h1 with | inl hX_in => exact hX_in | inr hcompl => have hP_in : f (S_of X hX_mem) ∈ P := mem_image_of_mem _ (mem_univ _) rw [mem_compl] at hcompl exact (hcompl hP_in).elim have hf_in_A : f (S_of X hX_mem) ∈ A := by simp only [A, mem_image, mem_attach, true_and, Subtype.exists] exact ⟨X, hX_mem, rfl⟩ have hf_in_sdiff : f (S_of X hX_mem) ∈ P \ A := hX_sub hf_in_X rw [mem_sdiff] at hf_in_sdiff exact hf_in_sdiff.2 hf_in_A
The set A has cardinality at least k.
Since A ⊆ P, card_sdiff_add_card_eq_card gives |P \ A| + |A| = |P|. Since |P| = k + s and |P \ A| ≤ s, linear arithmetic gives |A| = |P| - |P \ A| ≥ (k + s) - s = k.
uses
card_sdiff_add_card_eq_cardhave hk_le_A : k ≤ A.card := by have := card_sdiff_add_card_eq_card hAP omega
The set A must have cardinality strictly less than k, which contradicts |A| ≥ k and establishes the one-sided lower bound k + r ≤ |P|.
Suppose |A| ≥ k. By exists_subset_card_eq, pick a k-element subset T ⊆ A ⊆ P. The selector g chooses g(T) ∈ T ⊆ A. By definition of A, there is an (s+1)-subset X ⊆ P such that f(S(X)) = g(T), where S = S(X) = X ∪ Pᶜ. Because T ⊆ P, T is disjoint from Pᶜ, so S ∩ T = (X ∪ Pᶜ) ∩ T = X ∩ T. Thus |S ∩ T| = |X ∩ T| ≤ |X| = s + 1 ≤ r (using card_le_card and inter_subset_left). But by the separation hypothesis, |S ∩ T| ≤ r implies f(S) ≠ g(T), contradicting f(S) = g(T). Hence |A| < k, and combining this with k ≤ |A| yields False via omega, completing the proof of k + r ≤ |P|.
uses
exists_subset_card_eq,mem_powersetCard,card_le_card,inter_subset_lefthave hA_lt_k : A.card < k := by by_contra! hge obtain ⟨T, hTsub, hTcard⟩ := exists_subset_card_eq hge have hTP : T ⊆ P := hTsub.trans hAP have hg_in_A : g ⟨T, hTcard⟩ ∈ A := hTsub (hg ⟨T, hTcard⟩) simp only [A, mem_image, mem_attach, true_and, Subtype.exists] at hg_in_A obtain ⟨X, hX_mem, hf_eq⟩ := hg_in_A have hX' := mem_powersetCard.mp hX_mem let S := S_of X hX_mem let T_sub : {S : Finset (Fin (2*k-1)) // S.card = k} := ⟨T, hTcard⟩ have hinter : (S.val ∩ T_sub.val) = X ∩ T := by dsimp [S, S_of, T_sub] ext x simp only [mem_inter, mem_union, mem_compl] constructor · rintro ⟨h1 | h2, hxT⟩ · exact ⟨h1, hxT⟩ · exact (h2 (hTP hxT)).elim · rintro ⟨hxX, hxT⟩ exact ⟨Or.inl hxX, hxT⟩ have hcard_inter : (S.val ∩ T_sub.val).card ≤ r := by rw [hinter] have : (X ∩ T).card ≤ X.card := card_le_card inter_subset_left rw [hX'.2] at this omega have hne := hfg S T_sub hcard_inter exact hne hf_eq omega
Both selectors f and g each use at least k + r colors.
The lower bound k + r ≤ |im(f)| follows directly from op861_selector_palette_lower_bound_one_side. For g, we apply the one-sided lemma with g and f swapped. The swapped separation hypothesis requires that |S ∩ T| ≤ r implies g(S) ≠ f(T); by commutativity of intersection (Finset.inter_comm), |T ∩ S| = |S ∩ T| ≤ r, so the original hypothesis gives f(T) ≠ g(S), whose symmetry yields g(S) ≠ f(T).
uses
op861_selector_palette_lower_bound_one_side,Finset.inter_commrefine ⟨op861_selector_palette_lower_bound_one_side k r hk f g hf hg hfg, ?_⟩ apply op861_selector_palette_lower_bound_one_side k r hk g f hg hf intro S T hST rw [Finset.inter_comm] at hST exact (hfg T S hST).symm
card_compl- For a finite set s, the cardinality of its complement sᶜ is Fintype.card α - s.card.
Fintype.card_fin- The cardinality of the standard finite type Fin n is n.
exists_subset_card_eq- If n ≤ s.card, there exists a subset t ⊆ s with t.card = n.
mem_image_of_mem- If a ∈ s, then f(a) belongs to the image Finset.image f s.
mem_univ- Every element of a finite type belongs to the universal set Finset.univ.
mem_compl- An element belongs to the complement sᶜ if and only if it does not belong to s.
card_le_card- If s ⊆ t, then s.card ≤ t.card.
subset_univ- Every finite set in a finite type is a subset of Finset.univ.
card_univ- The cardinality of Finset.univ is Fintype.card α.
mem_powersetCard- A set s belongs to the n-element powerset of t if and only if s ⊆ t and s.card = n.
card_union_eq_card_add_card- For disjoint finite sets s and t, (s ∪ t).card = s.card + t.card.
sdiff_subset- The set difference s \ t is a subset of s.
mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
mem_sdiff- An element belongs to s \ t if and only if it belongs to s and does not belong to t.
card_sdiff_add_card_eq_card- If s ⊆ t, then (t \ s).card + s.card = t.card.
inter_subset_left- The intersection s₁ ∩ s₂ is a subset of s₁.
op861_selector_palette_lower_bound_one_side- Under the given hypotheses, the first selector f uses at least k + r colors.
Finset.inter_comm- Intersection of finite sets is commutative: s₁ ∩ s₂ = s₂ ∩ 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 Finset intheorem op861_selector_palette_lower_bound_one_side (k r : ℕ) (hk : 1 ≤ k) (f g : {S : Finset (Fin (2*k-1)) // S.card = k} → Fin (2*k-1)) (hf : ∀ S, f S ∈ S.val) (hg : ∀ S, g S ∈ S.val) (hfg : ∀ S T, (S.val ∩ T.val).card ≤ r → f S ≠ g T) : k + r ≤ (Finset.univ.image f).card := by set P := Finset.univ.image f have hk_le : k ≤ P.card := by by_contra! hlt have hcompl : k ≤ Pᶜ.card := by rw [card_compl, Fintype.card_fin] omega obtain ⟨t, ht_sub, ht_card⟩ := exists_subset_card_eq hcompl let S : {S : Finset (Fin (2*k-1)) // S.card = k} := ⟨t, ht_card⟩ have hfS_in_compl : f S ∈ Pᶜ := ht_sub (hf S) have hfS_in_P : f S ∈ P := mem_image_of_mem _ (mem_univ S) rw [mem_compl] at hfS_in_compl exact hfS_in_compl hfS_in_P by_contra! hlt set s := P.card - k have hPcard : P.card = k + s := by omega have hsr : s + 1 ≤ r := by omega have hPle : P.card ≤ 2 * k - 1 := by have h1 := card_le_card (subset_univ P) rw [card_univ, Fintype.card_fin] at h1 exact h1 have hc : Pᶜ.card = k - 1 - s := by rw [card_compl, Fintype.card_fin, hPcard] omega let S_of : (X : Finset (Fin (2*k-1))) → X ∈ P.powersetCard (s + 1) → {S : Finset (Fin (2*k-1)) // S.card = k} := fun X hX => have hX' := mem_powersetCard.mp hX have hdisj : Disjoint X Pᶜ := disjoint_compl_right.mono_left hX'.1 ⟨X ∪ Pᶜ, by rw [card_union_eq_card_add_card.2 hdisj, hX'.2, hc]; omega⟩ let A := (P.powersetCard (s + 1)).attach.image (fun ⟨X, hX⟩ => f (S_of X hX)) have hAP : A ⊆ P := by intro a ha simp only [A, mem_image, mem_attach, true_and, Subtype.exists] at ha obtain ⟨X, hX, rfl⟩ := ha exact mem_image_of_mem _ (mem_univ _) have hdiff : (P \ A).card ≤ s := by by_contra! hgt obtain ⟨X, hX_sub, hX_card⟩ := exists_subset_card_eq hgt have hXP : X ⊆ P := hX_sub.trans sdiff_subset have hX_mem : X ∈ P.powersetCard (s + 1) := by rw [mem_powersetCard] exact ⟨hXP, hX_card⟩ have hf_in_X : f (S_of X hX_mem) ∈ X := by have h1 : f (S_of X hX_mem) ∈ (S_of X hX_mem).val := hf _ rw [mem_union] at h1 cases h1 with | inl hX_in => exact hX_in | inr hcompl => have hP_in : f (S_of X hX_mem) ∈ P := mem_image_of_mem _ (mem_univ _) rw [mem_compl] at hcompl exact (hcompl hP_in).elim have hf_in_A : f (S_of X hX_mem) ∈ A := by simp only [A, mem_image, mem_attach, true_and, Subtype.exists] exact ⟨X, hX_mem, rfl⟩ have hf_in_sdiff : f (S_of X hX_mem) ∈ P \ A := hX_sub hf_in_X rw [mem_sdiff] at hf_in_sdiff exact hf_in_sdiff.2 hf_in_A have hk_le_A : k ≤ A.card := by have := card_sdiff_add_card_eq_card hAP omega have hA_lt_k : A.card < k := by by_contra! hge obtain ⟨T, hTsub, hTcard⟩ := exists_subset_card_eq hge have hTP : T ⊆ P := hTsub.trans hAP have hg_in_A : g ⟨T, hTcard⟩ ∈ A := hTsub (hg ⟨T, hTcard⟩) simp only [A, mem_image, mem_attach, true_and, Subtype.exists] at hg_in_A obtain ⟨X, hX_mem, hf_eq⟩ := hg_in_A have hX' := mem_powersetCard.mp hX_mem let S := S_of X hX_mem let T_sub : {S : Finset (Fin (2*k-1)) // S.card = k} := ⟨T, hTcard⟩ have hinter : (S.val ∩ T_sub.val) = X ∩ T := by dsimp [S, S_of, T_sub] ext x simp only [mem_inter, mem_union, mem_compl] constructor · rintro ⟨h1 | h2, hxT⟩ · exact ⟨h1, hxT⟩ · exact (h2 (hTP hxT)).elim · rintro ⟨hxX, hxT⟩ exact ⟨Or.inl hxX, hxT⟩ have hcard_inter : (S.val ∩ T_sub.val).card ≤ r := by rw [hinter] have : (X ∩ T).card ≤ X.card := card_le_card inter_subset_left rw [hX'.2] at this omega have hne := hfg S T_sub hcard_inter exact hne hf_eq omegatheorem op861_selector_palette_lower_bound (k r : ℕ) (hk : 1 ≤ k) (f g : {S : Finset (Fin (2*k-1)) // S.card = k} → Fin (2*k-1)) (hf : ∀ S, f S ∈ S.val) (hg : ∀ S, g S ∈ S.val) (hfg : ∀ S T, (S.val ∩ T.val).card ≤ r → f S ≠ g T) : k+r ≤ (Finset.univ.image f).card ∧ k+r ≤ (Finset.univ.image g).card := by refine ⟨op861_selector_palette_lower_bound_one_side k r hk f g hf hg hfg, ?_⟩ apply op861_selector_palette_lower_bound_one_side k r hk g f hg hf intro S T hST rw [Finset.inter_comm] at hST exact (hfg T S hST).symm