---

Claim. J. W. Moon and L. Moser, On cliques in graphs, Israel J. Math. 3 (1965), no. 1, 23--28, define a clique as a maximal complete subgraph and $g(n)$ as the maximum number of different sizes of cliques in a graph with $n$ nodes (p. 23), and prove two bounds, with all logarithms to the base $2$ (p. 25). Theorem 3 (p. 25; paged at theorem_3): $g(n)\ge n-[\log n]-2[\log\log n]-4$, which the paper introduces as the improvement over $g(n)\ge[\frac12(n+1)]$ once $n\ge26$; the proof is an explicit graph of complete blocks whose clique sizes run through every intermediate value, with display (6), $g(n)\ge n-2[\log n]-1$ for all $n$ (proof omitted), covering $n<47$. Theorem 4 (p. 27; paged at theorem_4): "If $n\ge4$, then $g(n)\le n-[\log n]$." The proof counts cliques through their intersections with the nodes outside a largest clique.

Covers. Bounds on $g(n)$ for Problem 927: the lower bound $g(n)\ge n-[\log_2n]-2[\log_2\log_2n]-4$ for $n\ge26$ and the upper bound $g(n)\le n-[\log_2n]$ for $n\ge4$. The upper bound is the upper half of the estimate $g(n)=n-\log_2n+O(1)$, whose lower half is Spencer's bound. Not covered: the iterated-logarithm question, which Spencer's bound refutes.

Depends on. Nothing in this wiki; the result rests on the cited paper alone.

Acceptance. Refereed: Israel Journal of Mathematics, volume 3, issue 1, pp. 23--28, issued March 1965 (the day is the issue's nominal first day, used for this page's date). The site's commentary attributes both bounds to the paper, 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 (p. 23), the statements of Theorems 3 and 4 and of display (6) (pp. 25 and 27) and the proof of Theorem 4 (pp. 27--28); the proof of Theorem 3 is taken for its structure only, and nothing is independently reviewed in this corpus.