On the distinct maximal-clique sizes in $k$-uniform hypergraphs

Abstract

Let $g(n,k)$ be the maximum number of distinct sizes of maximal cliques in an $n$-vertex $k$-uniform hypergraph, and let $f(n,k)=n-g(n,k)$. We determine the asymptotic order of $f(n,k)$ for every fixed integer $k\ge 3$. Define $L_2(x)=\max \{2,{\log }_2(\max \{1,x\})\}$, and, for $j\ge 3$, let $L_j(x)$ be the least number of iterations of $L_{j-1}$ needed to reach a value at most $16$. We prove that $$f(n,k)={\Theta }_k(L_k(n)).$$ In particular, $f(n,3)=\Theta ({\log }^{\ast }n)$, where ${\log }^{\ast }n$ denotes the iterated logarithm. We also determine the asymptotic behaviour of the layered-tree threshold $c(n,k)$ arising from Gao's insertion-tree method: $$c(n,k)={\log }_2{L}_k(n)+O_k(1).$$ Consequently, $f(n,k)={\Theta }_k\left(2^{c(n,k)}\right)$. Our result gives a negative answer to Gao's question in the case $k=3$.

10 pages, no figures; comments welcome