Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.