Problem Statement
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)?
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)?
Categories:
Graph Theory
Progress
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].
Source: erdosproblems.com/803 | Last verified: January 16, 2026