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

Abstract

Let $g(n,k)$ be the largest possible number of distinct sizes of maximal cliques in a $k$-uniform hypergraph on $n$ vertices, and let $f(n,k)=n-g(n,k)$. In the graph case, Spencer proved in 1971 that $f(n,2)=\hat{I}˜(\log n)$. For $3$-uniform hypergraphs, Erdős constructed examples showing that $f(n,3)\le {\log }^{\ast }n+O(1)$, where ${\log }^{\ast }n$ is the number of iterated logarithms such that $\log \log \dots \log n<1$. Recently, Gao (JCT-B, 2026) proved that $f(n,3)\ge \log {\log }^{\ast }n-O(1)$, thereby answering a question posed by Erdős. In the same paper, Gao defined the associated layered-tree threshold $c(n,3)$ and asked whether $f(n,k)=\hat{I}˜(c(n,3))$. In this paper, we determine the correct order $$f(n,3)=\hat{I}˜({\log }^{\ast }n).$$ Since $c(n,3)=\log {\log }^{\ast }n+O(1)$, our result gives a negative answer to Gao's question in the case $k=3$. We conclude by proposing the following conjecture: $f(n,k)=\hat{I}{˜}_k\left(2^{c(n,k)}\right)$ for every fixed $k\ge 3$.

10 pages, no figures; comments welcome

Topics & keywords