14
$\begingroup$

$\text{ex} (n;G)$ is the maximal number of edges of a graph of order $n$ can have without containing $G$ as a subgraph.

There are theorems saying what the limit actually is. But my lecture notes says that it is not hard to see that this ratio converges as $n$ tends to infinity.

Can anyone point out why I should expect this ratio to converge?

  • 0
    in the remaining $K_n$, the "red density" is at most $a$. Then so that the overall proportion exceeds $a$, more than$a$proportion of $a$ edges incident at $v$ must be red, which must be true for every vertex. Then inside any $K_n$, at every vertex, the "red density" is greater than $(an-1)/(n-1)$, this is very close to $a$ for $n$ large but still$a$little bit less. And i am stuck.2012-12-29

3 Answers 3

2

It is true that $\operatorname{ex}(n; G)/\binom{n}{2}$ is monotone non-increasing. As you've observed, if you have a graph on $n$ vertices of density $\theta$, removing just any vertex doesn't give you a subgraph of density $\theta$. However, it is true that there exists some vertex whose removal gives you a subgraph of density at least $\theta$, as the following "averaging argument" makes precise.

(Throughout the proof, $E(G)$ denotes the edge set of a graph $G$, and $e(G) := \lvert E(G) \rvert$ denotes the number of edges in $G$.)

Proof: Let $G$ be a graph. Let $F$ be a graph on $n$ vertices. Define $\theta := \frac{e(F)}{\dbinom{n}{2}}$ to be the density of $F$.

Now choose $n - 1$ vertices of $F$ uniformly at random, and consider the subgraph $H$ induced by these vertices. There are $n$ choices for $H$, and an edge $uv$ of $F$ is in $H$ as long as both $u$ and $v$ are vertices of $H$. Hence, for all $e \in E(F)$, we have $\mathbb{P}\bigl( e \in E(H)\bigr) = \frac{n-2}{n}.$ This means that the expected number of edges in $H$ is $\mathbb{E}\bigl(e(H)\bigr) = \sum_{e \in E(F)} \mathbb{P}\bigl(e \in E(H)\bigr) = \frac{n-2}{n} e(F) = \frac{n-2}{n} \theta\dbinom{n}{2} = \theta\dbinom{n-1}{2}.$ Because $H$ has $n - 1$ vertices, this means that the expected density of $H$ is $\theta$. Since the average density of $H$ is $\theta$, there must exist a choice of $H$ (call it $H_0$) with density at least $\theta$.

Because $H_0$ is a graph on $n - 1$ vertices, if $\theta > \operatorname{ex}(n - 1; G)/\binom{n - 1}{2}$, then by definition $H_0$ must contain a copy of $G$, which means that and $F$ does as well. We have thus shown that every graph on $n$ vertices of density $\theta > \operatorname{ex}(n - 1; G)/\binom{n - 1}{2}$ must contain a copy of $G$. This implies that $\frac{\operatorname{ex}(n; G)}{\dbinom{n}{2}} \leq \frac{\operatorname{ex}(n - 1; G)}{\dbinom{n-1}{2}},$ as claimed. $\square$

Note: this proof is based on an argument in this survey paper by Peter Keevash (see Section 2).

  • 0
    Thanks for the correction. Yes, I mixed up $G$ and $H$. Too bad comments can't be edited.2013-11-11
1

Let $H$ be a $G$-free graph with $n$ vertices ($n\gt2$) and $e(n;G)$ edges, and let $p$ be the number of pairs $(e,v)$ such that $e$ is an edge of $H$ and $v$ is a vertex of $H$ not incident with $e$. Choosing $e$ first we see that $p=e(n;G)(n-2)$. Choosing $v$ first we see that $p\le ne(n-1;G)$. Hence $e(n;G)(n-2)\le ne(n-1;G)$, i.e., $e(n;G)/\binom n2\le e(n-1;G)/\binom{n-1}2$.

-3

If you look at the numerator, there are $\frac{n^2}{2}$ possible edges in an undirected graph, and it seems intuitive that this number $ex(n,G)$ would grow like a constant factor of this. So we say the numerator is $\Theta(n^2)$.

For the denominator, we see that $\binom{n}{2} = n(n-1) = n^2 - n$, which is $\Theta(n^2)$.

The $\Theta$ notation basically means that both functions grow like $n^2$ does, and you can reason that if two things grow at basically the same rate, then their quotient will converge. For a reference on this notation, see this wikipedia article.

  • 1
    You did not show that the limit exists2012-12-28