# Bounds for maximal blowup contained in graph

In my homework, I'm asked to prove the following: By denoting $b_n(r,\epsilon)$ - the largest integer $b$ so that any graph with $(1-\frac{1}{r} +\epsilon)\frac{n^2}{2}$ edges, contains a $b$-blowup of $K_{r+1}$ (meaning, that it contains a complete $r+1$-partite graph, with $b$ vertices in each partition). I need to show that $b_n(1,\epsilon)=\Theta\left(\frac{\log n}{\log(1/\epsilon)}\right)$ and that $b_n(2,\epsilon)=O\left(\frac{\log n}{\log(1/\epsilon)}\right)$.

First, I'm not sure how to show either the lower bound, or the upper bound. For the first part, I know that $ex(n; K_{b,b}) \geq c\binom{n}{2}^{1-\frac{1}{t+1}}$ and $ex(n; K_{b,b}) \leq cb^{\frac{1}{b}}n^{2-\frac{1}{b}}$ and I think that for one of the bounds I need to combine one of those inequalities, with the fact that for $\epsilon\binom{n}{2}$ there is a bipartite graph.

I'll appreciate any light you can shed on the subject.

-

Well, it's a good idea and I've kind of thought of it already, but it gives the lower bound only - $b > \frac{logn}{log(1/\epsilon)}$. And even then, it requires some fine tuning on the constants. –  Pavel Dec 1 '12 at 19:05