Erdős Problem #146 — 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}.$

Erdős’s conjecture, posed in 1967, asks whether every fixed bipartite $r$-degenerate graph $H$ satisfies $\operatorname{ex}(n,H)=O(n^{2-1/r})$, including the $r=2$ case.

Known results

• Alon, Krivelevich, and Sudakov (2003): $\operatorname{ex}(n,H)=O(n^{2-1/(4r)})$ for every fixed bipartite $r$-degenerate $H$.
• Alon, Krivelevich, and Sudakov (2003): the conjectured $O(n^{2-1/r})$ bound holds when one bipartition class has maximum degree at most $r$.
• The conjectured bound is known for broad families, including $r$-degenerate blow-ups of trees.
• For $r=2$, a $C_4$-free one-sided degree-$2$ case has a stronger bound $O(n^{3/2-\delta})$.

2026 refutation claim

A Lean 4 development claims that for every $r\ge2$ there is a connected bipartite graph of degeneracy exactly $r$ with $\operatorname{ex}(n,H_r)\ge c n^{2-1/r+1/(28r^2)}$ for all sufficiently large $n$. If correct, this refutes the conjecture; the claim is unverified.

Current status (as of 2026): the conjecture is not independently settled, while a formalized 2026 development claims counterexamples for every $r\ge2$.