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}$.
Ilya
- 251
- 3
- 9