Problem Statement
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$?
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$?
Categories:
Graph Theory
Progress
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].Source: erdosproblems.com/804 | Last verified: January 16, 2026