PROVED
This has been solved in the affirmative.
- $100
For any $\epsilon>0$ there exists $\delta=\delta(\epsilon)>0$ such that if $G$ is a graph on $n$ vertices with no independent set or clique of size $\geq \epsilon\log n$ then $G$ contains an induced subgraph with $m$ edges for all $m\leq \delta n^2$.
Conjectured by Erdős and McKay, who proved it with $\delta n^2$ replaced by $\delta (\log n)^2$. Solved by Kwan, Sah, Sauermann, and Sawhney
[KSSS22]. Erdős' original formulation also had the condition that $G$ has $\gg n^2$ edges, but an old result of Erdős and Szemerédi says that this follows from the other condition anyway.
View the LaTeX source
Additional thanks to: Zachary Hunter and Mehtaab Sawhney
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 #88, https://www.erdosproblems.com/88, accessed 2026-02-13
