I need to prove that the maximum number of edges in a $n \times n$ bipartite graph, that doens't have a complete bipartite subgraph $K_{r,r}$ is lower bounded by $cn^{2-2/(r+1)}$ where c is a constant that can only depend on r and not on n.
I know this problem is related with probabilistic proofs, and I am trying to find the expected number of edges in a bipartite graph ($n \times n$) that is in a graph with such stated property because I think that the $n^2$ part is probably related to "for all possible edges in the graph", but I can't go on with the proof.
Any hints? :)
Thanks.