Problem #572: Show that for $k\geq 3$\[\mathrm{ex}(n;C_{2k})\gg...

---

Progress

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). Erdős and Klein [Er38] proved $\mathrm{ex}(n;C_4)\asymp n^{3/2}$.

Erdős [Er64c] and Bondy and Simonovits [BoSi74] showed that\[\mathrm{ex}(n;C_{2k})\ll kn^{1+\frac{1}{k}}.\]Benson [Be66] has proved this conjecture for $k=3$ and $k=5$. 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. See [LUW99] for further history and references.

See also [765] and the entry in the graphs problem collection.