Erdős Problem #713

declared status 'open'. Formalized: no. Is it true that, for every bipartite graph $G$, there exists some $\alpha\in [1,2)$ and $c>0$ such that$$\mathrm{ex}(n;G)\sim cn^\alpha?$$Must $\alpha$ be rational? Current best: Erd\H{o}s sometimes asked this in the weaker version with just$$\mathrm{ex}(n;G)\asymp n^{\alpha}.$$Erd\H{o}s [Er67d] had initially conjectured that, for any bipartite graph $G$, $\mathrm{ex}(n;G)\sim cn^{\alpha}$ for some constant $c>0$ and $\alpha$ of the shape $1+\frac{1}{k}$ or $2-\frac{1}{k}$ for some integer $k\geq 2$. A simplified proof was given by F\"{u}redi and Gerbner [FuGe21], who extended it to a counterexample for all $k\geq 5$. Prize: $500. Tags: graph theory, turan number.

Notation is rendered from the stored source. The pinned checkout remains the exact record.