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.

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.

share|improve this question
add comment

2 Answers

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

share|improve this answer
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
add comment

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.

share|improve this answer
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
add comment

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.