Logo
All Random Solved Random Open
OPEN
Let $\epsilon>0$ and $n$ be sufficiently large. Show that, if $G$ is a graph on $n$ vertices which does not contain $K_{2,2,2}$ and $G$ has at least $\epsilon n^2$ many edges, then $G$ contains an independent set on $\gg_\epsilon n$ many vertices.
A problem of Erdős, Hajnal, Sós, and Szemerédi.

See also the entry in the graphs problem collection.