Problem Statement
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$?
In particular, is there such a graph for $g(n)=(\log n)^3$?
Categories:
Graph Theory
Progress
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].
Source: erdosproblems.com/805 | Last verified: January 16, 2026