SOLVED
Let $g(n)$ be the maximum number of different sizes of cliques that can occur in a graph on $n$ vertices. Estimate $g(n)$ - in particular, is it true that
\[g(n)=n-\log_2n-\log_*(n)+O(1),\]
where $\log_*(n)$ is the number of iterated logarithms such that $\log\cdots \log n <1$.
A quantity first considered by Moon and Moser
[MoMo65], who proved
\[n-\log_2n-2\log\log n<g(n)\leq n-\lfloor \log_2 n\rfloor.\]
Erdős
[Er66b] improved the lower bound to
\[n-\log_2 n-\log_*(n)-O(1)<g(n)\]
and conjectured this was the correct order of magnitude.
This was disproved by Spencer [Sp71], who proved that in fact
\[g(n) > n-\log_2 n-O(1).\]
See also [775].
