linear_family_bounded_transversal_kernel
Given a finite linear set family, a transversal B, a subfamily P, and a cover budget q, retain P and at most q+1 sets through each point of B. Every transversal of size at most q for the retained subfamily covers the whole family.
Statement
theorem linear_family_bounded_transversal_kernel {α : Type*} [DecidableEq α] (H P : Finset (Finset α)) (B : Finset α) (q : ℕ) (hP : P ⊆ H) (hl : ∀ A ∈ H, ∀ D ∈ H, A ≠ D → (A ∩ D).card ≤ 1) (hB : ∀ A ∈ H, ¬Disjoint A B) : ∃ F : Finset (Finset α), F ⊆ H ∧ P ⊆ F ∧ F.card ≤ P.card + B.card * (q + 1) ∧ ∀ C : Finset α, C.card ≤ q → (∀ A ∈ F, ¬Disjoint A C) → (∀ A ∈ H, ¬Disjoint A C)
- Source
- Related sunflower and triangle-kernel reductions: https://link.springer.com/article/10.1007/s00453-022-00986-0 and https://arxiv.org/abs/2308.16515. This is a structural helper for the triangle packing-cover campaign, with no claim of novelty.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- linear_book_forces_centerIn a finite linear family of sets all containing a fixed point, every transversal smaller than the family contains that point.
The proof, explained
The theorem constructs a kernel for small transversals in a linear set family H: starting from a preserved subfamily P, we retain for each vertex b in a known transversal B at most q + 1 sets containing b. If a small transversal C of the retained family F missed some set A ∈ H, picking a point b ∈ A ∩ B yields a contradiction: if the degree of b is at most q, then A was retained in F and is therefore covered; if the degree of b exceeds q, the retained sets form a linear book of size q + 1 > |C|, which forces the center b itself to belong to C and hence intersects A.
Construct a candidate kernel family F = P ∪ ⋃_{b ∈ B} R(b) by selecting up to q + 1 sets containing each vertex b ∈ B, reducing the proof to four subgoals.
For each point b, there exists a subcollection R(b) of sets in H containing b with cardinality min(|{A ∈ H | b ∈ A}|, q + 1) via Finset.exists_subset_card_eq and min_le_left. Defining F as the union of P and the sets R(b) for b ∈ B reduces the existential goal to proving F ⊆ H, P ⊆ F, the size bound on F, and that every small transversal of F hits all of H.
uses
Finset.exists_subset_card_eq,min_le_leftclassical have hex : ∀ b : α, ∃ R : Finset (Finset α), R ⊆ H.filter (fun A => b ∈ A) ∧ R.card = min (H.filter (fun A => b ∈ A)).card (q + 1) := by intro b exact Finset.exists_subset_card_eq (min_le_left _ _) choose R hR hRc using hex let F := P ∪ B.biUnion R refine ⟨F, ?_, ?_, ?_, ?_⟩
F ⊆ H.
Every element A ∈ F is either in P, which is a subset of H by assumption, or in R(b) for some b ∈ B, which consists solely of sets in H containing b.
uses
Finset.mem_union.mp,Finset.mem_biUnion.mp,Finset.mem_filter.mp· intro A hA rcases Finset.mem_union.mp hA with hp | hb · exact hP hp · obtain ⟨b, _, hb⟩ := Finset.mem_biUnion.mp hb exact (Finset.mem_filter.mp (hR b hb)).1
P ⊆ F.
Since F is defined as P ∪ ⋃_{b ∈ B} R(b), any set in P belongs to F by definition of union.
uses
Finset.mem_union_left· intro A hA exact Finset.mem_union_left _ hA
|F| ≤ |P| + |B| * (q + 1).
By the union bound, |F| ≤ |P| + |⋃_{b ∈ B} R(b)| ≤ |P| + ∑_{b ∈ B} |R(b)|. Since each |R(b)| = min(|H_b|, q + 1) ≤ q + 1, summing this bound over all b ∈ B gives at most |B| * (q + 1).
uses
Finset.card_union_le,Nat.add_le_add_left,Finset.card_biUnion_le,Finset.sum_le_sum,min_le_right· calc F.card ≤ P.card + (B.biUnion R).card := Finset.card_union_le _ _ _ ≤ P.card + ∑ b ∈ B, (R b).card := Nat.add_le_add_left Finset.card_biUnion_le _ _ ≤ P.card + B.card * (q + 1) := by apply Nat.add_le_add_left calc (∑ b ∈ B, (R b).card) ≤ ∑ _b ∈ B, (q + 1) := by apply Finset.sum_le_sum intro b _ rw [hRc b] exact min_le_right _ _ _ = B.card * (q + 1) := by simp
Given a transversal C of F with |C| ≤ q, if some A ∈ H were disjoint from C, then there is a point b ∈ A ∩ B such that C intersects every set in R(b).
Assume for contradiction that A ∈ H is disjoint from C. Since B is a transversal of H, A and B are not disjoint, so there exists b ∈ A ∩ B. For this b, every set D ∈ R(b) belongs to F by construction, so C must intersect D because C is a transversal of F.
uses
Finset.not_disjoint_iff.mp,Finset.mem_union_right,Finset.mem_biUnion.mpr· intro C hC hcover A hA by_contra hd obtain ⟨b, hbA, hbB⟩ := Finset.not_disjoint_iff.mp (hB A hA) let Q := H.filter (fun D => b ∈ D) have hRQ : R b ⊆ Q := hR b have hRcovered : ∀ D ∈ R b, ¬Disjoint D C := by intro D hD apply hcover D exact Finset.mem_union_right _ (Finset.mem_biUnion.mpr ⟨b, hbB, hD⟩)
If at most q sets in H contain b, a contradiction is reached.
Let Q be the family of sets in H containing b. If |Q| ≤ q, then |Q| ≤ q + 1, which implies min(|Q|, q + 1) = |Q|. Since R(b) ⊆ Q and |R(b)| = |Q|, we have R(b) = Q. Thus A ∈ Q = R(b), so C must intersect A, contradicting that A and C are disjoint.
uses
Finset.eq_of_subset_of_card_le,min_eq_left,Nat.le_trans,Nat.le_succ,Finset.mem_filter.mprby_cases hsmall : Q.card ≤ q · have hEq : R b = Q := by apply Finset.eq_of_subset_of_card_le hRQ rw [hRc b] simp [Q, min_eq_left (Nat.le_trans hsmall (Nat.le_succ q))] have hAR : A ∈ R b := by rw [hEq] exact Finset.mem_filter.mpr ⟨hA, hbA⟩ exact hRcovered A hAR hd
If more than q sets in H contain b, a contradiction is reached, completing the proof.
When |Q| ≥ q + 1, we have |R(b)| = q + 1 > |C|. The family R(b) is a linear book with center b (all sets contain b, and pairwise intersections have size at most 1). Since |C| < |R(b)| and C intersects every leaf of the book, linear_book_forces_center implies b ∈ C. But b ∈ A, so A and C share b, contradicting their disjointness.
uses
min_eq_right,linear_book_forces_center,Finset.mem_filter.mp,Finset.not_disjoint_iff.mpr· have hbig : C.card < (R b).card := by rw [hRc b] have : q + 1 ≤ Q.card := by omega simp only [Q, min_eq_right this] omega have hcenter : b ∈ C := by apply linear_book_forces_center (R b) b C · intro D hD exact (Finset.mem_filter.mp (hRQ hD)).2 · intro D hD E hE hDE exact hl D (Finset.mem_filter.mp (hRQ hD)).1 E (Finset.mem_filter.mp (hRQ hE)).1 hDE · exact hRcovered · exact hbig exact (Finset.not_disjoint_iff.mpr ⟨b, hbA, hcenter⟩) hd
Finset.card_biUnion_le- The cardinality of a union of sets indexed by a finite set is bounded by the sum of their cardinalities: |⋃_{i ∈ s} t(i)| ≤ ∑_{i ∈ s} |t(i)|.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities: |s ∪ t| ≤ |s| + |t|.
Finset.eq_of_subset_of_card_le- If a subset s ⊆ t of finite sets satisfies |t| ≤ |s|, then s = t.
Finset.exists_subset_card_eq- A finite set s contains a subset of cardinality n whenever n ≤ |s|.
Finset.mem_biUnion.mp- An element belongs to ⋃_{i ∈ s} t(i) if and only if it belongs to t(i) for some i ∈ s (forward direction).
Finset.mem_biUnion.mpr- If an element belongs to t(i) for some i ∈ s, it belongs to ⋃_{j ∈ s} t(j).
Finset.mem_filter.mp- An element in a filtered set {x ∈ s | p(x)} belongs to s and satisfies p.
Finset.mem_filter.mpr- If an element belongs to s and satisfies p, it belongs to the filtered set {x ∈ s | p(x)}.
Finset.mem_union.mp- An element in s ∪ t belongs to s or belongs to t.
Finset.mem_union_left- If an element belongs to s, it belongs to s ∪ t.
Finset.mem_union_right- If an element belongs to t, it belongs to s ∪ t.
Finset.not_disjoint_iff.mp- If two finite sets are not disjoint, they share at least one common element.
Finset.not_disjoint_iff.mpr- If two finite sets share a common element, they are not disjoint.
Finset.sum_le_sum- If f(i) ≤ g(i) for all i in a finite set s, then ∑_{i ∈ s} f(i) ≤ ∑_{i ∈ s} g(i).
linear_book_forces_center- In a linear family of sets all sharing a vertex b, any transversal with fewer vertices than sets must contain b.
min_eq_left- If a ≤ b, then min(a, b) = a.
min_eq_right- If b ≤ a, then min(a, b) = b.
min_le_left- The minimum min(a, b) is less than or equal to a.
min_le_right- The minimum min(a, b) is less than or equal to b.
Nat.add_le_add_left- Adding the same natural number to both sides of an inequality preserves it: n ≤ m implies k + n ≤ k + m.
Nat.le_succ- Every natural number n is at most its successor: n ≤ n + 1.
Nat.le_trans- Inequality on natural numbers is transitive: n ≤ m and m ≤ k imply n ≤ k.
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 1000000theorem linear_family_bounded_transversal_kernel {α : Type*} [DecidableEq α] (H P : Finset (Finset α)) (B : Finset α) (q : ℕ) (hP : P ⊆ H) (hl : ∀ A ∈ H, ∀ D ∈ H, A ≠ D → (A ∩ D).card ≤ 1) (hB : ∀ A ∈ H, ¬Disjoint A B) : ∃ F : Finset (Finset α), F ⊆ H ∧ P ⊆ F ∧ F.card ≤ P.card + B.card * (q + 1) ∧ ∀ C : Finset α, C.card ≤ q → (∀ A ∈ F, ¬Disjoint A C) → (∀ A ∈ H, ¬Disjoint A C) := by classical have hex : ∀ b : α, ∃ R : Finset (Finset α), R ⊆ H.filter (fun A => b ∈ A) ∧ R.card = min (H.filter (fun A => b ∈ A)).card (q + 1) := by intro b exact Finset.exists_subset_card_eq (min_le_left _ _) choose R hR hRc using hex let F := P ∪ B.biUnion R refine ⟨F, ?_, ?_, ?_, ?_⟩ · intro A hA rcases Finset.mem_union.mp hA with hp | hb · exact hP hp · obtain ⟨b, _, hb⟩ := Finset.mem_biUnion.mp hb exact (Finset.mem_filter.mp (hR b hb)).1 · intro A hA exact Finset.mem_union_left _ hA · calc F.card ≤ P.card + (B.biUnion R).card := Finset.card_union_le _ _ _ ≤ P.card + ∑ b ∈ B, (R b).card := Nat.add_le_add_left Finset.card_biUnion_le _ _ ≤ P.card + B.card * (q + 1) := by apply Nat.add_le_add_left calc (∑ b ∈ B, (R b).card) ≤ ∑ _b ∈ B, (q + 1) := by apply Finset.sum_le_sum intro b _ rw [hRc b] exact min_le_right _ _ _ = B.card * (q + 1) := by simp · intro C hC hcover A hA by_contra hd obtain ⟨b, hbA, hbB⟩ := Finset.not_disjoint_iff.mp (hB A hA) let Q := H.filter (fun D => b ∈ D) have hRQ : R b ⊆ Q := hR b have hRcovered : ∀ D ∈ R b, ¬Disjoint D C := by intro D hD apply hcover D exact Finset.mem_union_right _ (Finset.mem_biUnion.mpr ⟨b, hbB, hD⟩) by_cases hsmall : Q.card ≤ q · have hEq : R b = Q := by apply Finset.eq_of_subset_of_card_le hRQ rw [hRc b] simp [Q, min_eq_left (Nat.le_trans hsmall (Nat.le_succ q))] have hAR : A ∈ R b := by rw [hEq] exact Finset.mem_filter.mpr ⟨hA, hbA⟩ exact hRcovered A hAR hd · have hbig : C.card < (R b).card := by rw [hRc b] have : q + 1 ≤ Q.card := by omega simp only [Q, min_eq_right this] omega have hcenter : b ∈ C := by apply linear_book_forces_center (R b) b C · intro D hD exact (Finset.mem_filter.mp (hRQ hD)).2 · intro D hD E hE hDE exact hl D (Finset.mem_filter.mp (hRQ hD)).1 E (Finset.mem_filter.mp (hRQ hE)).1 hDE · exact hRcovered · exact hbig exact (Finset.not_disjoint_iff.mpr ⟨b, hbA, hcenter⟩) hd