Logo
All Random Solved Random Open
SOLVED
Give an asymptotic formula for $\mathrm{ex}(n;C_4)$.
Erdős and Klein [Er38] proved $\mathrm{ex}(n;C_4)\asymp n^{3/2}$. Reiman [Re58] proved \[\frac{1}{2\sqrt{2}}\leq \lim \frac{\mathrm{ex}(n;C_4)}{n^{3/2}}\leq \frac{1}{2}.\] Erdős and Rényi, and independently Brown, gave a construction that proved if $n=q^2+q+1$, where $q$ is a prime power, then \[\mathrm{ex}(n;C_4)\geq\frac{1}{2}q(q+1)^2.\] Coupled with the upper bound of Reiman this implies that $\mathrm{ex}(n;C_4)\sim\frac{1}{2}n^{3/2}$ for all large $n$. Füredi [Fu83] proved that if $q>13$ then \[\mathrm{ex}(n;C_4)=\frac{1}{2}q(q+1)^2.\]

See also [572].

Additional thanks to: Rishika Agrawal