---

Claim. P. Erdős, On cliques in graphs, Israel J. Math. 4 (1966), no. 4, 233--234, with a clique a maximal complete subgraph, $g(n)$ the maximum number of different sizes of cliques in a graph of $n$ vertices, logarithms to the base $2$, $\log_kn$ the $k$-fold iterated logarithm and $H(n)$ the least integer with $\log_{H(n)}n<2$, proves the Theorem (p. 233; paged at theorem):

$$g(n)\ge n-\log n-H(n)-O(1).$$

The proof is an explicit construction in the style of Moon and Moser (pp. 233--234), three classes of vertices whose sizes are chosen so that the graph has a clique of every size between a bounded value and $[n-\log n-H(n)]$. The note improves the lower bound $n-[\log n]-2[\log\log n]-4$ of Moon and Moser, and Erdős adds that the theorem seems likely to be close to best possible, though he could not prove that $g(n)-(n-\log n)$ tends to infinity; the conjecture the site records is his later restatement of 1969.

Covers. The lower bound $g(n)\ge n-\log_2n-H(n)-O(1)$ for Problem 927: this is the lower half of the conjectured formula $g(n)=n-\log_2n-\log_*(n)+O(1)$, since $H(n)$ and $\log_*(n)$ differ by a bounded amount. Not covered: the formula's upper half, which Spencer's bound refutes.

Depends on. Nothing in this wiki; the construction is explicit and the result rests on the cited paper alone.

Acceptance. Refereed: Israel Journal of Mathematics, volume 4, issue 4, pp. 233--234, issued December 1966 (the day is the issue's nominal first day, used for this page's date). The site's commentary records the improvement, but the curator's label credits Spencer's disproof, so no reviewed evidence is listed. The source has a library source card.

Read depth. The page rests on the definitions, display (1), the definition of $H(n)$, the Theorem and the remarks (pp. 233--234); the construction is taken for its structure only, and nothing is independently reviewed in this corpus.