On cliques in graphs (Q5971413)

A complete subgraph of a graph \(G\) is called a clique if it is not contained in any other complete subgraph of \(G\). Let \(g(n)\) denote the maximum number of different sizes of cliques that can occur in a graph with \(n\) points: if \(\log_k n\) denotes the \(k\)-times iterated logarithm to the base 2 of \(n\), let \(H = H(n)\) be the smallest integer such that \(\log_H n < 2\). The author shows that \(g(n) \geq n-\log n-H(n)-O(1)\). This extends an earlier result of the reviewer and \textit{L.Moser} [Isr. J. Math. 3, 23-28 (1965; Zbl 0144.23205)].