Erdős Problem #803

We call a graph \(H\) \(D\)-balanced (or \(D\)-almost-regular) if the maximum degree of \(H\) is at most \(D\) times the minimum degree of \(H\). Is it true that for every \(m\geq 1\), if \(n\) is sufficiently large, any graph on \(n\) vertices with \(\geq n\log n\) edges contains a \(O(1)\)-balanced subgraph with \(m\) vertices and \(\gg m\log m\) edges (where the implied constants are absolute)? A problem of Erdős and Simonovits [ErSi70]. 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. See also [1077](https://www.erdosproblems.com/1077).