DISPROVED
This has been solved in the negative.
Let $f(m,n)$ be maximal such that any graph on $n$ vertices in which every induced subgraph on $m$ vertices has an independent set of size at least $\log n$ must contain an independent set of size at least $f(n)$.
Estimate $f(n)$. In particular, is it true that $f((\log n)^2,n) \geq n^{1/2-o(1)}$? Is it true that $f((\log n)^3,n)\gg (\log n)^3$?
A question of Erdős and Hajnal. Alon and Sudakov
[AlSu07] proved that in fact\[\frac{(\log n)^2}{\log\log n}\ll f((\log n)^2,n) \ll (\log n)^2\]and\[f((\log n)^3,n)\asymp \frac{(\log n)^2}{\log\log n}.\]See also
[805].
View the LaTeX source
Additional thanks to: Noga Alon
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 #804, https://www.erdosproblems.com/804, accessed 2026-01-14
