intersecting_uniform_hypergraph_card_le_pow
Let α be a type with decidable equality and let k ≥ 1 be a natural number. Let ℱ be a finite family of finite subsets of α such that every F ∈ ℱ has cardinality k. Suppose that for all F1, F2 ∈ ℱ, the intersection F1 ∩ F2 is nonempty, and that for every finite subset A of α with cardinality less than k, there exists F ∈ ℱ such that A and F are disjoint. Then the cardinality of ℱ is at most k^k.
Statement
theorem intersecting_uniform_hypergraph_card_le_pow {α : Type*} [DecidableEq α] (k : ℕ) (hk : 1 ≤ k) (ℱ : Finset (Finset α)) (hunif : ∀ F ∈ ℱ, F.card = k) (hinter : ∀ F1 ∈ ℱ, ∀ F2 ∈ ℱ, (F1 ∩ F2).Nonempty) (htau : ∀ (A : Finset α), A.card < k → ∃ F ∈ ℱ, Disjoint A F) : ℱ.card ≤ k ^ k
- Formalizes
- arXiv:2610.37315 Theorem 1.1 -- The maximum size of intersecting k-graphs with covering number k
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- exists_mem_card_filter_subset_le_mulLet α be a type with decidable equality, let k ≥ 1 be a natural number, and let ℱ be a finite family of finite subsets of α such that for…
- card_filter_subset_le_one_of_card_eqLet α be a type with decidable equality, let k be a natural number, and let ℱ be a finite family of finite subsets of α such that every F…
- Used by 1
- op_639_intersecting_four_uniform_covering_four_card_le_two_hundred_fifty_sixLet V be a finite type with decidable equality, and let F be a family of 4-element subsets of V. If F is pairwise intersecting, has no…
Read back from the Lean
Let α be a type with decidable equality, and let k be a natural number such that 1 ≤ k. Let ℱ be a finite set of finite subsets of α (Finset (Finset α)). Suppose that:
1. Every member F ∈ ℱ has cardinality k (hunif),
2. For all F1, F2 ∈ ℱ, the intersection F1 ∩ F2 is nonempty (hinter), and
3. For every finite subset A of α with A.card < k, there exists some F ∈ ℱ such that A and F are disjoint (htau).
Then the cardinality of ℱ is at most k ^ k.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by induction on m ≤ k to show the stronger claim that any set A of cardinality k - m is contained in at most k^m hyperedges of ℱ. The base case m = 0 holds because every hyperedge has size k, so any set of size k is contained in at most one hyperedge. For the inductive step, given A of size k - (m + 1) < k, the covering number hypothesis provides an edge F ∈ ℱ disjoint from A; since all edges pairwise intersect, an averaging argument selects a vertex x ∈ F disjoint from A such that the number of edges containing A is at most k times the number containing A ∪ {x}. The induction hypothesis applied to A ∪ {x}, which has size k - m, then bounds this count by k * k^m = k^(m + 1). Finally, setting m = k and A = ∅ yields |ℱ| ≤ k^k.
Base case: any set of cardinality k is contained in at most k^0 = 1 hyperedge of ℱ
We set up an induction on m ≤ k to show that any set A of size k - m is contained in at most k^m hyperedges. In the base case m = 0, A has cardinality k - 0 = k. Since every hyperedge in ℱ has cardinality k, at most one hyperedge can contain A by card_filter_subset_le_one_of_card_eq, which matches the bound 1 = k^0 by pow_zero.
uses
card_filter_subset_le_one_of_card_eq,pow_zerohave hind : ∀ m ≤ k, ∀ (A : Finset α), A.card = k - m → (ℱ.filter (fun F => A ⊆ F)).card ≤ k ^ m := by intro m induction m with | zero => intro _ A hA have hAk : A.card = k := by omega have hle1 := card_filter_subset_le_one_of_card_eq k ℱ hunif A hAk simp only [pow_zero] exact hle1
For any set A of cardinality k - (m + 1), there exists an element x ∉ A such that the number of hyperedges containing A is at most k times the number containing A ∪ {x}
Assuming m + 1 ≤ k and |A| = k - (m + 1), we have |A| < k. By hypothesis htau, there exists a hyperedge F ∈ ℱ disjoint from A. Because |F| = k and every hyperedge in ℱ intersects F, lemma exists_mem_card_filter_subset_le_mul provides a vertex x ∈ F such that the number of hyperedges containing A is at most k times the number containing A ∪ {x}. Since F and A are disjoint, Finset.disjoint_left.mp guarantees that x ∉ A.
uses
exists_mem_card_filter_subset_le_mul,Finset.disjoint_left.mp| succ m ih => intro hmk A hA have hlt : A.card < k := by omega obtain ⟨F, hF, hdisj⟩ := htau A hlt have hFcard : F.card = k := hunif F hF obtain ⟨x, hxF, hle⟩ := exists_mem_card_filter_subset_le_mul k hk ℱ A F hinter hF hFcard have hxnot : x ∉ A := fun hxA => Finset.disjoint_left.mp hdisj hxA hxFInductive step: any set A of cardinality k - (m + 1) is contained in at most k^(m + 1) hyperedges of ℱ
Since x ∉ A, the cardinality of A ∪ {x} is |A| + 1 = k - m by Finset.card_insert_of_notMem. The induction hypothesis applies to A ∪ {x}, showing that at most k^m hyperedges contain A ∪ {x}. Multiplying this inequality by k via Nat.mul_le_mul_left and simplifying k * k^m = k^(m + 1) completes the inductive step.
uses
Finset.card_insert_of_notMem,Nat.mul_le_mul_lefthave hcard_succ : (insert x A).card = k - m := by rw [Finset.card_insert_of_notMem hxnot, hA] omega have hmk' : m ≤ k := by omega have hih := ih hmk' (insert x A) hcard_succ calc (ℱ.filter (fun F => A ⊆ F)).card _ ≤ k * (ℱ.filter (fun F => insert x A ⊆ F)).card := hle _ ≤ k * k ^ m := Nat.mul_le_mul_left k hih _ = k ^ (m + 1) := by ring
The cardinality of ℱ is at most k^k
We specialize the inductive claim to m = k and the empty set A = ∅, using le_rfl for k ≤ k. The empty set has cardinality 0 = k - k, and every hyperedge in ℱ contains ∅, so the subcollection of hyperedges containing ∅ is all of ℱ. This yields |ℱ| ≤ k^k.
uses
le_rflhave h0 : (∅ : Finset α).card = k - k := by simp have h_filter : (ℱ.filter (fun F => (∅ : Finset α) ⊆ F)) = ℱ := by ext F simp have h_final := hind k le_rfl ∅ h0 rw [h_filter] at h_final exact h_final
card_filter_subset_le_one_of_card_eq- in a k-uniform hypergraph, any subset of size k is contained in at most one hyperedge
pow_zero- any element raised to the power 0 equals 1
exists_mem_card_filter_subset_le_mul- in an intersecting k-uniform hypergraph, for any set A and hyperedge F, there is an element x ∈ F such that the number of hyperedges containing A is at most k times the number of hyperedges containing A ∪ {x}
Finset.disjoint_left.mp- if two sets are disjoint, any element in the first set does not belong to the second
Finset.card_insert_of_notMem- inserting an element not already in a finite set increases its cardinality by 1
Nat.mul_le_mul_left- multiplying both sides of an inequality of natural numbers by k preserves the inequality
le_rfl- the inequality relation ≤ is reflexive (a ≤ a)
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.
/-- The size of an intersecting k-uniform hypergraph with covering number k is at most k^k. -/theorem intersecting_uniform_hypergraph_card_le_pow {α : Type*} [DecidableEq α] (k : ℕ) (hk : 1 ≤ k) (ℱ : Finset (Finset α)) (hunif : ∀ F ∈ ℱ, F.card = k) (hinter : ∀ F1 ∈ ℱ, ∀ F2 ∈ ℱ, (F1 ∩ F2).Nonempty) (htau : ∀ (A : Finset α), A.card < k → ∃ F ∈ ℱ, Disjoint A F) : ℱ.card ≤ k ^ k := by have hind : ∀ m ≤ k, ∀ (A : Finset α), A.card = k - m → (ℱ.filter (fun F => A ⊆ F)).card ≤ k ^ m := by intro m induction m with | zero => intro _ A hA have hAk : A.card = k := by omega have hle1 := card_filter_subset_le_one_of_card_eq k ℱ hunif A hAk simp only [pow_zero] exact hle1 | succ m ih => intro hmk A hA have hlt : A.card < k := by omega obtain ⟨F, hF, hdisj⟩ := htau A hlt have hFcard : F.card = k := hunif F hF obtain ⟨x, hxF, hle⟩ := exists_mem_card_filter_subset_le_mul k hk ℱ A F hinter hF hFcard have hxnot : x ∉ A := fun hxA => Finset.disjoint_left.mp hdisj hxA hxF have hcard_succ : (insert x A).card = k - m := by rw [Finset.card_insert_of_notMem hxnot, hA] omega have hmk' : m ≤ k := by omega have hih := ih hmk' (insert x A) hcard_succ calc (ℱ.filter (fun F => A ⊆ F)).card _ ≤ k * (ℱ.filter (fun F => insert x A ⊆ F)).card := hle _ ≤ k * k ^ m := Nat.mul_le_mul_left k hih _ = k ^ (m + 1) := by ring have h0 : (∅ : Finset α).card = k - k := by simp have h_filter : (ℱ.filter (fun F => (∅ : Finset α) ⊆ F)) = ℱ := by ext F simp have h_final := hind k le_rfl ∅ h0 rw [h_filter] at h_final exact h_final