I find out that this problem is a special case of Zarankiewicz problem and it was solved by Bollobas in 2004. The answer is $ex(n,n,C_4)\sim n^{3/2}$.
Ilya
- 251
- 3
- 9