Problem 572

Erdős Problem #572: declared status 'open'. Formalized: no. Show that for $k\geq 3$$$\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{1}{k}}.$$ Current best: It is easy to see that $\mathrm{ex}(n;C_{2k+1})=\lfloor n^2/4\rfloor$ for any $k\geq 1$ (and $n>2k+1$) (since no bipartite graph contains an odd cycle). Lazebnik, Ustimenko, and Woldar [LUW95] have shown that, for arbitrary $k\geq 3$,$$\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{2}{3k-3+\nu}},$$where $\nu=0$ if $k$ is odd and $\nu=1$ if $k$ is even. Prize: no. Tags: graph theory, turan number.