Problem Statement
If $G$ is a graph on $n$ vertices containing no independent set on $>n^{1/2}$ vertices then there is a set of $\leq n^{1/2}$ vertices containing $\gg n^{1/2}\log n$ edges.
Categories:
Graph Theory Ramsey Theory
Progress
Proved by Alon [Al96b].Source: erdosproblems.com/801 | Last verified: January 16, 2026