Claims

../

1965_03_01_moon_moser: Moon and Moser (Israel J. Math. 1965) bound g(n) below by n − [log n] − 2[log log n] − 4 and above by n − [log n], logarithms base 2; the upper half of the estimate g(n) = n − log_2 n + O(1); refereed.

1966_12_01_erdos: Erdős (Israel J. Math. 1966) proves g(n) ≥ n − log_2 n − H(n) − O(1), with H(n) the least k for which the k-fold iterated logarithm of n is below 2; the lower half of the conjectured formula; refereed.

1971_02_01_spencer: Spencer (Israel J. Math. 1971) builds, for every N > 33000, a graph on N vertices with at least N − log_2 N − 4 clique sizes as the paper states (one fewer in one case by its own counts), refuting the iterated-logarithm term.

---