For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge?

Solution 1:

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

Solution 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$.