OPEN
This is open, and cannot be resolved with a finite computation.
For which functions $g(n)$ with $n>g(n)\geq (\log n)^2$ is there a graph on $n$ vertices in which every induced subgraph on $g(n)$ vertices contains a clique of size $\geq \log n$ and an independent set of size $\geq \log n$?
In particular, is there such a graph for $g(n)=(\log n)^3$?
A problem of Erdős and Hajnal, who thought that there is no such graph for $g(n)=(\log n)^3$. Alon and Sudakov
[AlSu07] proved that there is no such graph with\[g(n)=\frac{c}{\log\log n}(\log n)^3\]for some constant $c>0$.
Alon, Bucić, and Sudakov
[ABS21] construct such a graph with\[g(n)\leq 2^{2^{(\log\log n)^{1/2+o(1)}}}.\]See also
[804].
View the LaTeX source
Additional thanks to: Zach Hunter
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 #805, https://www.erdosproblems.com/805, accessed 2025-12-07
