Bounds for maximal blowup contained in graph

Question

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.

Thanks in advance.

Answer 1

I have a feeling we are in the same class. If I understand correctly, we defined a b-blowup to be an addition of b vertices to each original vertex, and each of the new ones is connected only to the neighbors of the original vertex. So a b blowup of K_(2) is the graph K_(1,b) and not K_(b,b).

Answer 2

Your definition is correct and I managed to sovle the problem now using the bounds you posted. Just take them and "ask" for which values of b are the bounds achieved, i.e when is ex(n;Kb,b)≥c(n^2)1−1t+1 > ϵn^22.