AFTD Auto-Formalizing Theoretical Domains

linear_family_high_degree_neighborhood_obstruction

theoremverified

In a finite linear family, if B has more than q points and each point of B lies in more than q members, every set hitting all members that meet B has more than q points.

Statement

theorem linear_family_high_degree_neighborhood_obstruction {α : Type*} [DecidableEq α]
    (H : Finset (Finset α)) (B C : Finset α) (q : ℕ)
    (hl : ∀ A ∈ H, ∀ D ∈ H, A ≠ D → (A ∩ D).card ≤ 1)
    (hB : q < B.card)
    (hdeg : ∀ b ∈ B, q < (H.filter (fun A => b ∈ A)).card)
    (hcover : ∀ A ∈ H, ¬Disjoint A B → ¬Disjoint A C) : q < C.card
Source
Structural helper for the triangle packing-cover campaign; related matching-cover reductions are in https://arxiv.org/abs/2610.15269, Lemma 2.3. Finite checks and limitations are recorded in state/campaigns/triangle_reductions/high_codegree_route_in512.md.
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

We argue by contradiction, assuming |C| ≤ q. For any point b ∈ B, the family of sets in H containing b forms a linear book centered at b with strictly more than q members. Every such member meets B at b and therefore also meets C, which forces the center b to belong to C by the linear book lemma. This implies B ⊆ C, giving q < |B| ≤ |C| ≤ q, a contradiction.

  1. Assume for contradiction that |C| ≤ q.

    We assume the negation of the conclusion q < |C|. By Nat.le_of_not_gt, ¬(q < |C|) implies |C| ≤ q.

    lines 11–13

    uses Nat.le_of_not_gt

      classical
      by_contra hn
      have hc : C.card ≤ q := Nat.le_of_not_gt hn
  2. Every element of B belongs to C, so B ⊆ C.

    Fix an arbitrary point b ∈ B and let Q be the family of sets in H containing b. We apply linear_book_forces_center to Q, b, and C, verifying its four hypotheses: 1. Every member of Q contains b by definition of Q (Finset.mem_filter.mp). 2. Any two distinct members of Q intersect in at most one point, which holds because H is linear. 3. Every member A ∈ Q intersects C: since b ∈ A ∩ B, A and B are not disjoint (Finset.not_disjoint_iff.mpr), so the covering hypothesis hcover implies A and C are not disjoint. 4. |C| is strictly less than |Q|: using lt_of_le_of_lt on |C| ≤ q and the degree bound q < |Q| (from hdeg). The lemma forces b ∈ C, and since b was arbitrary, B ⊆ C.

    lines 14–26

    uses linear_book_forces_center, Finset.mem_filter.mp, Finset.not_disjoint_iff.mpr, lt_of_le_of_lt

      have hsub : B ⊆ C := by
        intro b hb
        let Q := H.filter (fun A => b ∈ A)
        apply linear_book_forces_center Q b C
        · intro A hA
          exact (Finset.mem_filter.mp hA).2
        · intro A hA D hD hAD
          exact hl A (Finset.mem_filter.mp hA).1 D (Finset.mem_filter.mp hD).1 hAD
        · intro A hA
          have h := Finset.mem_filter.mp hA
          apply hcover A h.1
          exact Finset.not_disjoint_iff.mpr ⟨b, h.2, hb⟩
        · exact lt_of_le_of_lt hc (hdeg b hb)
  3. The inclusion B ⊆ C yields a contradiction.

    Because B ⊆ C, Finset.card_le_card gives |B| ≤ |C|. Combined with q < |B| and |C| ≤ q, this yields q < |B| ≤ |C| ≤ q, which is an immediate linear arithmetic contradiction closed by omega.

    lines 27–28

    uses Finset.card_le_card

      have hcard := Finset.card_le_card hsub
      omega
Nat.le_of_not_gt
If a natural number is not strictly greater than another, it is less than or equal to it.
linear_book_forces_center
In a linear hypergraph where every edge contains a common vertex b, if a set C intersects every edge and |C| is strictly less than the number of edges, then b must be in C.
Finset.mem_filter.mp
An element in a filtered finset belongs to the original finset and satisfies the selection predicate.
Finset.not_disjoint_iff.mpr
If two finsets share a common element, then they are not disjoint.
lt_of_le_of_lt
If a ≤ b and b < c, then a < c.
Finset.card_le_card
A subset has cardinality at most that of the superset.

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 1000000set_option maxRecDepth 4000theorem linear_family_high_degree_neighborhood_obstruction {α : Type*} [DecidableEq α]    (H : Finset (Finset α)) (B C : Finset α) (q : ℕ)    (hl : ∀ A ∈ H, ∀ D ∈ H, A ≠ D → (A ∩ D).card ≤ 1)    (hB : q < B.card)    (hdeg : ∀ b ∈ B, q < (H.filter (fun A => b ∈ A)).card)    (hcover : ∀ A ∈ H, ¬Disjoint A B → ¬Disjoint A C) : q < C.card := by  classical  by_contra hn  have hc : C.card ≤ q := Nat.le_of_not_gt hn  have hsub : B ⊆ C := by    intro b hb    let Q := H.filter (fun A => b ∈ A)    apply linear_book_forces_center Q b C    · intro A hA      exact (Finset.mem_filter.mp hA).2    · intro A hA D hD hAD      exact hl A (Finset.mem_filter.mp hA).1 D (Finset.mem_filter.mp hD).1 hAD    · intro A hA      have h := Finset.mem_filter.mp hA      apply hcover A h.1      exact Finset.not_disjoint_iff.mpr ⟨b, h.2, hb⟩    · exact lt_of_le_of_lt hc (hdeg b hb)  have hcard := Finset.card_le_card hsub  omega
See it in the graphDiscuss this resultChallenge it