Logo
All Random Solved Random Open
OPEN - $500
If $H$ is bipartite and is $r$-degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$, then \[\mathrm{ex}(n;H) \ll n^{2-1/r}.\]
Conjectured by Erdős and Simonovits. Open even for $r=3$. Alon, Krivelevich, and Sudakov [AKS03] have proved \[\mathrm{ex}(n;H) \ll n^{2-1/4r}.\] They also prove the full Erdős-Simonovits conjectured bound if $H$ is bipartite and the maximum degree in one component is $r$.

See also [113] and [147].

See also the entry in the graphs problem collection.