Logo
All Random Solved Random Open
SOLVED - $500
If $G$ is bipartite then $\mathrm{ex}(n;G)\ll n^{3/2}$ if and only $G$ is $2$-degenerate, that is, $G$ contains no induced subgraph with minimal degree at least 3.
Conjectured by Erdős and Simonovits [ErSi84]. Erdős first offered \$250 for a proof and \$100 for a counterexample, but in [Er93] offered \$500 for a counterexample.

Disproved by Janzer [Ja21] who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that \[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

See also [146] and [147] and the entry in the graphs problem collection.

Additional thanks to: Zachary Hunter