op869_many_shared_colors
If |B| < |A| and every element of A meets at least d elements of B, then at least d elements of B lie in at least two of the sets.
Statement
theorem op869_many_shared_colors {α β : Type} [DecidableEq β] (A : Finset α) (B : Finset β) (E : α → Finset β) (d : ℕ) (hE : ∀ x ∈ A, E x ⊆ B) (hd : ∀ x ∈ A, d ≤ (E x).card) (hab : B.card < A.card) : d ≤ (B.filter (fun u => 2 ≤ (A.filter (fun x => u ∈ E x)).card)).card
- Source
- arXiv:2610.41516, Lemma 2.2 (the case i = 2)
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- op869_double_countDouble counting in a bipartite incidence: if every element x of A meets at least d elements of B, then for i ≤ |A|, |A|·d ≤ |B|·(i-1) +…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
The proof, explained
The theorem is proved by applying a double-counting inequality with threshold i = 2. The case d = 0 is trivial, while d > 0 together with |B| < |A| implies |A| ≥ 2, validating the double-counting bound |A| · d ≤ |B| + (|A| - 1) · b₂, where b₂ counts the elements of B shared by at least two sets. Assuming for contradiction that fewer than d elements are shared, algebraic rearrangement leads to |A| ≤ |B|, which directly contradicts |B| < |A|.
The inequality holds trivially when d = 0.
We split into cases based on whether d = 0 or d > 0 using Nat.eq_zero_or_pos. When d = 0, the inequality 0 ≤ |{u ∈ B | 2 ≤ |{x ∈ A | u ∈ E(x)}|}| holds immediately because cardinalities are non-negative.
uses
Nat.eq_zero_or_posrcases Nat.eq_zero_or_pos d with hd0 | hd0 · omega
The cardinality of A is at least 2.
When d > 0, since |B| < |A|, the set A must have positive cardinality and is therefore nonempty by Finset.card_pos.mp. Picking an element x ∈ A, we have 1 ≤ d ≤ |E(x)| by le_trans. Because E(x) ⊆ B, Finset.card_le_card gives |E(x)| ≤ |B|, so 1 ≤ |B|. Combining this with |B| < |A| yields |A| ≥ 2.
uses
Finset.card_pos.mp,le_trans,Finset.card_le_cardhave hA2 : 2 ≤ A.card := by obtain ⟨x, hx⟩ : A.Nonempty := Finset.card_pos.mp (by omega) have h1 : 1 ≤ (E x).card := le_trans hd0 (hd x hx) have h2 := Finset.card_le_card (hE x hx) omega
The double-counting inequality applies for threshold i = 2.
We apply the helper theorem op869_double_count with threshold i = 2, which is valid because 2 ≤ |A|. Abbreviating the number of elements of B that belong to at least two of the sets E(x) as b₂, the lemma yields |A| · d ≤ |B| · (2 - 1) + (|A| - 2 + 1) · b₂.
uses
op869_double_counthave h := op869_double_count A B E d 2 hE hd hA2 set b2 := (B.filter (fun u => 2 ≤ (A.filter (fun x => u ∈ E x)).card)).card
Assuming b₂ < d for contradiction, re-index |A| and d to simplify the double-counting bound.
We argue by contradiction and suppose b₂ < d. Since |A| ≥ 2 and d ≥ 1, we can write |A| = a' + 2 and d = d' + 1 for natural numbers a' and d'. Substituting these representations into the double-counting bound and simplifying (a' + 2) - 2 to a' with Nat.add_sub_cancel gives (a' + 2)(d' + 1) ≤ |B| + (a' + 1) · b₂, while the contradiction hypothesis becomes b₂ ≤ d'.
uses
Nat.add_sub_cancelby_contra hlt push Not at hlt obtain ⟨a', ha'⟩ : ∃ a', A.card = a' + 2 := ⟨A.card - 2, by omega⟩ obtain ⟨d', hd'⟩ : ∃ d', d = d' + 1 := ⟨d - 1, by omega⟩ rw [ha', hd'] at h rw [hd'] at hlt simp only [Nat.add_sub_cancel] at h
The assumption b₂ < d implies |A| ≤ |B|, contradicting |B| < |A|.
From b₂ ≤ d', multiplying both sides by a' + 1 with Nat.mul_le_mul_left gives (a' + 1) · b₂ ≤ (a' + 1) · d'. Combined with the simplified double-counting inequality, this yields (a' + 2)(d' + 1) ≤ |B| + (a' + 1) · d'. Expanding the left-hand side as (a' + 1) · d' + a' + d' + 2 and canceling (a' + 1) · d' shows that |A| + d' = a' + d' + 2 ≤ |B|. Since d' ≥ 0, this forces |A| ≤ |B|, directly contradicting the hypothesis |B| < |A|.
uses
Nat.mul_le_mul_lefthave h3 : (a' + 1) * b2 ≤ (a' + 1) * d' := Nat.mul_le_mul_left _ (by omega) nlinarith
Nat.eq_zero_or_pos- Every natural number is either zero or strictly positive.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most that of the other.
op869_double_count- If each subset E(x) ⊆ B has size at least d, then |A| · d ≤ |B|(i - 1) + (|A| - i + 1) · |{u ∈ B | |{x ∈ A | u ∈ E(x)}| ≥ i}| for any i ≤ |A|.
Nat.add_sub_cancel- Subtracting a number that was just added yields the original number: (n + m) - m = n.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a factor preserves the inequality.
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 op869_many_shared_colors {α β : Type} [DecidableEq β] (A : Finset α) (B : Finset β) (E : α → Finset β) (d : ℕ) (hE : ∀ x ∈ A, E x ⊆ B) (hd : ∀ x ∈ A, d ≤ (E x).card) (hab : B.card < A.card) : d ≤ (B.filter (fun u => 2 ≤ (A.filter (fun x => u ∈ E x)).card)).card := by rcases Nat.eq_zero_or_pos d with hd0 | hd0 · omega have hA2 : 2 ≤ A.card := by obtain ⟨x, hx⟩ : A.Nonempty := Finset.card_pos.mp (by omega) have h1 : 1 ≤ (E x).card := le_trans hd0 (hd x hx) have h2 := Finset.card_le_card (hE x hx) omega have h := op869_double_count A B E d 2 hE hd hA2 set b2 := (B.filter (fun u => 2 ≤ (A.filter (fun x => u ∈ E x)).card)).card by_contra hlt push Not at hlt obtain ⟨a', ha'⟩ : ∃ a', A.card = a' + 2 := ⟨A.card - 2, by omega⟩ obtain ⟨d', hd'⟩ : ∃ d', d = d' + 1 := ⟨d - 1, by omega⟩ rw [ha', hd'] at h rw [hd'] at hlt simp only [Nat.add_sub_cancel] at h have h3 : (a' + 1) * b2 ≤ (a' + 1) * d' := Nat.mul_le_mul_left _ (by omega) nlinarith