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.\]In [Er93] Erdős makes the stronger conjecture that, for all $n$,\[\mathrm{ex}(n;C_4)=\frac{n^{3/2}}{2}+\frac{n}{4}+O(n^{1/2}),\]although he said he 'never found any convincing evidence for [this] and would really be satisfied with\[\mathrm{ex}(n;C_4)=\frac{n^{3/2}}{2}+O(n).'\]Erdős [Er75] proved\[\mathrm{ex}(n;C_4)\leq \frac{n^{3/2}}{2}+\frac{n}{4}+O(n^{1/2}).\]Erdős's stronger conjecture was wrong - Ma and Yang [MaYa23] proved that, for some absolute constant $c>0$ and for a positive density set of $n$, in fact\[\mathrm{ex}(n;C_4)\leq \frac{n^{3/2}}{2}+\left(\frac{1}{4}-c\right)n.\]See also [572].

In [Er75] Erdős remarks that he first proved $\mathrm{ex}(n;C_4)\ll n^{3/2}$ while considering the number theoretic problem [425] in 1936, which predates Turán's study of extremal numbers by 5 years. As Erdős wrote: 'Being struck by a curious blindness and lack of imagination, I did not at that time extend the problem from $C_4$ to other graphs and thus missed founding an interesting and fruitful new branch of graph theory.'

View the LaTeX source

This page was last edited 14 October 2025.