Erdős Problem #113

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 [Ja23b] 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](https://www.erdosproblems.com/146) and [147](https://www.erdosproblems.com/147). The linked formal proof refutes the "only if" direction via Janzer's construction.