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

-

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.

-
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

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

-
Seems I was wrong about that. –  user38310 Dec 1 '12 at 17:01
Highly possible. After all, there are not that much extremal graph theory courses, commencing simultaneously around the world. Now, about the definition - the one that I have is the one I wrote. From the searches I made, this definition also coincides with the theory. –  Pavel Dec 1 '12 at 17:05