A problem of Erdős and Simonovits [ErSi70], who proved a similar claim replacing $\log n$ and $\log m$ by $n^{c}$ and $m^c$ respectively, for any constant $c>0$ (where the balance parameter may depend on $c$). (See [1077].)

Alon [Al08] proved this is false: for every $D>1$ and large $n$ there is a graph $G$ with $n$ vertices and $\geq n\log n$ edges such that if $H$ is a $D$-balanced subgraph then $H$ has $\ll m\sqrt{\log m}+\log D$ many edges.

Janzer and Sudakov [JaSu23] have proved that, for any $k$, if $n$ is sufficiently large then any graph on $n$ vertices with at least $n\log n$ edges contains a $O(1)$-balanced subgraph on $m\geq k$ vertices with\[\gg_k \frac{\sqrt{\log m}}{(\log\log m)^{3/2}}m\]many edges.

See also [1077].

View the LaTeX source

This page was last edited 07 October 2025.