Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
$\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?
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).
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$.
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.
