AFTD Auto-Formalizing Theoretical Domains

linear_family_bounded_transversal_kernel

theoremverified

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.

  1. 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.

    lines 13–21

    uses Finset.exists_subset_card_eq, min_le_left

      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, ?_, ?_, ?_, ?_⟩
  2. 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.

    lines 22–26

    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
  3. P ⊆ F.

    Since F is defined as P ∪ ⋃_{b ∈ B} R(b), any set in P belongs to F by definition of union.

    lines 27–28

    uses Finset.mem_union_left

      · intro A hA
        exact Finset.mem_union_left _ hA
  4. |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).

    lines 29–40

    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
  5. 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.

    lines 41–49

    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⟩)
  6. 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.

    lines 50–58

    uses Finset.eq_of_subset_of_card_le, min_eq_left, Nat.le_trans, Nat.le_succ, Finset.mem_filter.mpr

        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
  7. 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.

    lines 59–72

    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

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
See it in the graphDiscuss this resultChallenge it