Skip to content

Erdős problem 775

Is there a 33-uniform hypergraph on nn vertices which contains at least n−O(1)n-O(1) different sizes of cliques (maximal complete subgraphs)?

Sources

The source's own material, retained exactly.

4 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

775.lean

Retained formal statement2 of 4

The answer is no, as proved by Gao [Ga25]: more generally, for any k≥3k\geq 3, every kk-uniform hypergraph on nn vertices contains at most n−fk(n)n-f_k(n) different sizes of cliques, where fk(n)→∞f_k(n)\to \infty as n→∞n\to \infty.

FormalConjectures/ErdosProblems/775.leanErdos775.erdos_775.variants.gao3 linesExact file
∃ f,  Filter.Tendsto f Filter.atTop Filter.atTop ∧    ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (H : ThreeUniformHypergraph (Fin n)), H.cliqueSizes.ncard + f n ≤ n
SolvedStatement only, no proof