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?