Erdős constructed such a hypergraph with cliques of at least $n-\log_*n$ different sizes. For graphs, Spencer [Sp71] constructed a graph which contains cliques of at least $n-\log_2n+O(1)$ different sizes, which Moon and Moser [MoMo65] showed to be best possible.

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

See also [927].

View the LaTeX source

This page was last edited 17 October 2025.