Is it true that for every $m\geq 1$, if $n$ is sufficiently large, any graph on $n$ vertices with $\geq n\log_2n$ edges contains a $O(1)$-balanced subgraph with $m$ vertices and $\gg m\log m$ edges (where the implied constants are absolute)?
Is it true that for every $m\geq 1$, if $n$ is sufficiently large, any graph on $n$ vertices with $\geq n\log_2n$ edges contains a $O(1)$-balanced subgraph with $m$ vertices and $\gg m\log m$ edges (where the implied constants are absolute)?
Alon [Al08] proved this is actually false: for every $D>1$ and $n>10^5$ there is a graph $G$ with $\leq 2n$ vertices and $\geq 2n\log(2n)$ edges such that if $H$ is a $D$-balanced subgraph then $H$ has $\ll m(\sqrt{\log m}+\log D)$ many edges.