AFTD Auto-Formalizing Theoretical Domains

intersecting_uniform_hypergraph_card_le_pow

theoremverifiedformalization

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

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.

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

    lines 8–16

    uses card_filter_subset_le_one_of_card_eq, pow_zero

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

    lines 17–23

    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 hxF
  3. Inductive 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.

    lines 24–32

    uses Finset.card_insert_of_notMem, Nat.mul_le_mul_left

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

    lines 33–39

    uses le_rfl

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

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