# zarankiewicz problem lower bound

I was just reading through the following article: http://page.mi.fu-berlin.de/szabo/PDF/stoc96.pdf

On page 2 they give an explicit formula for the lower bound of the size of the graph.

Summary: We want to find a lower bound for the size of an $n\times n$ bipartite graph which does not contain the complete bipartite graph $K_{t,u}$

The size is at least $c' n^{2-\frac{t+u-2}{tu-1}}$. The article mentions it can be shown by some probabilistic method and refers to an article by Erdos but I cant find any proof in this paper, do you have some ideas?

-
What is the size of a graph? If it's the number of edges, then maybe it should say upper bound instead of lower bound, because the empty graph clearly has the property. – Zur Luria Jan 20 '14 at 20:29
Yes number of edges – Ulrich Otto Jan 20 '14 at 20:39