Erdős Problem 801: a small set with many edges
Statement and claim.
For every sufficiently large $n$, if an $n$-vertex graph has independence number at most $\sqrt n$, then some set of at most $\sqrt n$ vertices spans $\Omega(\sqrt n\log n)$ edges. We reconstruct Alon's proof, allowing the non-strict independence hypothesis in the displayed question:
https://web.math.princeton.edu/~nalon/PDFS/indrams1.pdf, Section 3. See
https://www.erdosproblems.com/801. The external input is the Ajtai--Komlós--Szemerédi triangle-free independence estimate: a triangle-free $v$-vertex graph of average degree $d\geq2$ has an independent set of size at least $c(v/d)\log d$, for an absolute $c>0$.
Two direct sampling cases.
Put $m=\lfloor\sqrt n\rfloor$, and let $\bar d$ be the average degree of $G$. If $\bar d\geq\sqrt n\log n$, a uniform $m$-vertex subset spans an expected \[
e(G)\frac{\binom m2}{\binom n2}
=\Omega(\sqrt n\log n)
\] edges, so one such subset suffices. Otherwise at least $n/2$ vertices have degree at most $2\sqrt n\log n$. Let $G'$ be their induced graph, so its maximum degree obeys that bound.
Suppose a neighbourhood in $G'$ spans at least $\sqrt n(\log n)^3$ edges. If the neighbourhood has at most $m$ vertices it already works. If it is larger, its order is at most $2\sqrt n\log n$, and a uniform $m$-subset has expected edge count at least a constant times \[
\sqrt n(\log n)^3
\frac{n}{n(\log n)^2}
=\sqrt n\log n.
\] Again the assertion follows.
Removing triangles after random sampling.
We may now assume every neighbourhood in $G'$ spans fewer than $\sqrt n(\log n)^3$ edges. Each triangle is counted in three neighbourhoods, so $G'$ has at most $n^{3/2}(\log n)^3$ triangles. Independently retain each vertex with probability $p=n^{-2/5}$. The expected retained vertex count minus the retained triangle count is at least \[
\frac n2p-n^{3/2}(\log n)^3p^3
=\frac12n^{3/5}-n^{3/10}(\log n)^3
\geq\frac14 n^{3/5}
\] for large $n$. Some sample attains this lower bound. Remove one vertex from each of its triangles, and then discard extra vertices if needed. We obtain a triangle-free induced subgraph $J$ of order $v=\lfloor n^{3/5}/4\rfloor$.
The independence bound forces enough edges.
Write $d$ for the average degree of $J$. First, the elementary bound $\alpha(J)\geq v/(d+1)$ and $\alpha(J)\leq\alpha(G)\leq\sqrt n$ show \[
d+1\geq v/\sqrt n=\Omega(n^{1/10}).
\] Thus $d\geq2$ and $\log d\geq c_1\log n$ for large $n$. The cited triangle-free theorem then gives \[
\sqrt n\geq\alpha(J)\geq c\frac vd\log d,
\qquad d\geq c_2n^{1/10}\log n.
\] Finally choose a uniform $m$-subset of $V(J)$. Its expected edge count is \[
\frac{vd}{2}\frac{\binom m2}{\binom v2}
=\Omega\left(\frac{dm^2}{v}\right)
=\Omega(\sqrt n\log n).
\] Some subset therefore has the required number of edges.
Scope.
All reductions, sampling arguments, and the transfer back to a set of at most $\sqrt n$ vertices are proved above. The full assertion uses only the explicitly stated triangle-free independence theorem as a substantial external input; the conclusion is not claimed for tiny $n$ where the asymptotic notation has no intended force.
Completion estimate.
COMPLETION: 100%