extremal_number
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