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

Thanks in advance.

-

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

-

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

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 13, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9513505697250366, "perplexity_flag": "head"}