Upper bounds on the extremal number of the 4-cycle

Abstract

We obtain some new upper bounds on the maximum number $f(n)$ of edges in $n$-vertex graphs without containing cycles of length four. This leads to an asymptotically optimal bound on $f(n)$ for a broad range of integers $n$ as well as a disproof of a conjecture of Erdős from 1970s which asserts that $f(n)=\frac{1}{2}{n}^{3/2}+\frac{1}{4}n+o(n)$.

11 pages, 1 figure