Erdős Problem #927

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_2 n - \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_2 n - 2 \log \log n < g(n) \le 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)\). Here \(\log_2 n\) and \(\log_*(n)\) are formalised as `Nat.log 2 n` and `Nat.iteratedLog 2 n` (iterating `Nat.log 2` until the value is at most `1`); both differ from the quantities in the problem by \(O(1)\), so the statement is unaffected. See also `erdos_775.variants.spencer` and `erdos_775.variants.moon_moser`.