Maximum number of edges in bipartite graph without cycles of length 4

Question

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?

Answer 1

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}$.

Answer 2

Just to point at the details: let the bipartition classes be X and Y. Now $\sum_{x\in X}\binom{\deg(x)}{2}$ counts the number of pairs in $Y$ with a common neighbour in $X$ (with multiplicity). But since no such pair has two common neighbours, the sum is at most $\binom{n}{2}$. By Jensen's inequality, the sum is minimised (for a given total $\sum_{x\in X}\deg(x)$ ) if and only if all vertices in $X$ have the same degree $e(G)/n$. Solving this equation gives the upper bound on $ex(n,n,C_4)$, with equality if and only if all degrees are the same and all pairs have exactly one common neighbour. Of course, point-line incidence graphs of projective planes satisfy both conditions: every point is on the same number of lines, and every pair of lines determines exactly one point. The general asymptotic then follows from the known results on the maximum gap between primes.