Let $ex(n,H)$ denote the maximum number of edges of a graph on $n$ vertices not containing a copy of $H$. Let $ex(n,m,H)$ denote the maximum number of edges of a bipartite graph with parts' sizes $m$ and $n$ not containing a copy of $H$.
I'm interested in upper bound on $ex(n, n, C_4)$. It is easy to show with probabilistic argument that $ex(n, n, C_4)\geq c\times n^{4/3}$. Also Erdös, Rényi, Sós (1954) showed that $ex(n,C_4)\sim\frac{1}{2}n^{3/2}$.
So, the question is if there exist a better upper bound for bipartite graph?
Best Answer
I find out that this problem is a special case of Zarankiewicz problem and it was solved by István Reiman in 1958 (thanks to Oliver Krüger for correction). The answer is $ex(n,n,C_4)\sim n^{3/2}$.