linear_family_high_degree_neighborhood_obstruction
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.
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.
uses
Nat.le_of_not_gtclassical by_contra hn have hc : C.card ≤ q := Nat.le_of_not_gt hn
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.
uses
linear_book_forces_center,Finset.mem_filter.mp,Finset.not_disjoint_iff.mpr,lt_of_le_of_lthave 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)
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.
uses
Finset.card_le_cardhave 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
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 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