Erdős Problem #714

declared status 'open'. Formalized: no. Is it true that$$\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?$$ Current best: K\"{o}v\'{a}ri, S\'{o}s, and Tur\'{a}n [KST54] proved$$\mathrm{ex}(n; K_{r,r}) \ll n^{2-1/r}$$for all $r\geq 2$. Brown [Br66] and, independently, Erd\H{o}s, R\'{e}nyi, and S\'{o}s [ERS66], proved the conjectured lower bound when $r=3$. When $r=2$ it is known that$$\mathrm{ex}(n;K_{2,2})=\left(\frac{1}{2}+o(1)\right)n^{3/2}$$(see [768], since $K_{2,2}=C_4$). Prize: no. Tags: graph theory, turan number.

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