Logo
All Random Solved Random Open
OPEN
Let $\delta>0$. If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_{2,2,2}$ and at least $\delta n^2$ edges then $G$ contains an independent set of size $\gg_\delta n$.
A problem of Erdős, Hajnal, Sós, and Szemerédi, who could prove this is true for $\delta>1/8$.

See also [533] and the entry in the graphs problem collection.