Let $\varepsilon<1/1000$ and $n$ is big enough. Is it true that every graph with at most $\varepsilon n^2$ edges has independence number bigger than $\varepsilon n$?



Independence number of graph with $\varepsilon n^2$ edges
No. Will's example is better, but you may also proceed probabilistically.


A random graph $G(n,\varepsilon)$ (every two vertices are joined with probability $\varepsilon$) has at most $\varepsilon n^2$ edges with probability almost 1 and does not have such huge independent sets, also with probability almost 1 (the probability of each set of size $\lceil \varepsilon n\rceil$ to be independent is small as $e^{-Cn^2}$, and the number of such sets is exponential in $n$.)


