Sign up ×
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:

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|cite|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.