1
$\begingroup$

Let H be a graph, and define $c_n(H) := \frac{ex(n, H)}{\frac{n(n-1)}{2}}$ Prove that $c_n(H) \leq c_{n−1}(H)$, and show that $\lim_{n→∞} c_n(H)$ exists.

So first of all, if we managed to show that the inequality holds, then this means that $(c_n(H))$ is a decreasing sequence bounded by $0$ and so the limit will exist.

The inequality is equivalent to $$\frac{ex(n, H)}{n} \leq \frac{ex(n-1, H)}{n-2}$$

I have no idea how to proceed. The only inequality I know about extremal graphs is that if $H$ has chromatic number $r+1$, then it certainly isn't $r$-partite so the Turan graph $T_r(n)$ will contain no copy of $H$. But this certainly won't work

Any hints/suggestions are appreciated

$\endgroup$
3
1
$\begingroup$

Hint: remove a vertex of minimum degree from a graph not containing $H$.

Proof: Suppose $G$ is a graph on $n$ vertices and $\text{ex}(n, H)$ edges that does not contain a copy of $H$. Then there is a vertex $v$ of $G$ of degree no more than $2\text{ex}(n, H)/n$, by a simple averaging argument. Upon deleting $v$, $G - v$ has at least $\text{ex}(n, H)(1-\frac{2}{n})$ edges and $n-1$ vertices, and $G-v$ also does not contain a copy of $H$. Thus $$ \text{ex}(n-1, H) \geq \text{ex}(n, H) (1-2/n) $$ and the desired inequality follows.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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