AFTD Auto-Formalizing Theoretical Domains

extremal_number

def

For a natural number n and a hypergraph F on vertex type W, the extremal number extremal_number n F is the maximum cardinality of an F-free 3-uniform hypergraph on Fin n (the supremum over all hypergraphs H on Fin n satisfying is_three_uniform H and is_hypergraph_free H F of H.card).

Statement

noncomputable def extremal_number (n : ℕ) {W : Type*} (F : Finset (Finset W)) : ℕ
Defined in
arXiv:2611.16654:94
Verified
13 Nov 2026
Axioms
none listed
Built on 2
  • is_three_uniformA hypergraph F (a finite family of finite sets of vertices) is 3-uniform if every hyperedge e in F has cardinality 3.
  • is_hypergraph_freeA hypergraph H on vertex set Fin n is F-free if there does not exist an embedding f : W ↪ Fin n such that every hyperedge e in F maps…

Read back from the Lean

Given a natural number n, a type W, and a hypergraph F : Finset (Finset W), extremal_number n F is the maximum cardinality H.card (or 0 if no such H exists) among all hypergraphs H : Finset (Finset (Fin n)) such that: 1. H is 3-uniform: every hyperedge e ∈ H has cardinality 3; and 2. H is F-free: there does not exist an injective map f : W ↪ Fin n such that for every hyperedge e ∈ F, the mapped hyperedge e.map f belongs to H.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The Turán extremal number ex(n, F) for 3-uniform hypergraphs: the maximum number of edges in an F-free 3-uniform hypergraph on n vertices. -/
noncomputable def extremal_number (n : ℕ) {W : Type*} (F : Finset (Finset W)) : ℕ := open scoped Classical in
  Finset.sup (Finset.univ.filter fun H : Finset (Finset (Fin n)) => is_three_uniform H ∧ is_hypergraph_free H F)
    Finset.card
See it in the graphDiscuss this resultChallenge it