Revision history of
146. All highlighted changes are compared to the current version.
Current version
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
[ErSi84]. Open even for $r=2$. 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 side of the bipartition is $r$.
See also
[113] and
[147].
This problem is
#43 in Extremal Graph Theory in the graphs problem collection.
2025-10-20 00:00:00
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
[ErSi84]. Open even for $r=2$. 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 is $r$.
See also
[113] and
[147].
ry in the graphs problem collection
