DISPROVED
This has been solved in the negative.
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_2n-\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_2n-2\log\log n<g(n)\leq 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).\]See also
[775].
View the LaTeX source
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #927, https://www.erdosproblems.com/927, accessed 2026-04-11
