$\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?

  • $\begingroup$ Its a nice question $\endgroup$
    – Amr
    Dec 26 '12 at 23:40
  • $\begingroup$ I'm not really sure about the general case, but it's not too bad if $G$ is connected. If $M$ is some $n$-vertex graph with the maximal number of edges such that $M$ doesn't contain $G$, then by taking the disjoint union of two copies of $M$, we would see that $ex(2n;G) \ge 2ex(n;G)$, and similarly for other positive integer multiples of $n$. then just observe that the variation of $ex(k;G)$ for $mn \le k \le (m+1)n$ must decrease as $m \in \mathbb{N}$ gets large, because adding one more vertex with no new edges doesn't change the ratio as much as $m$ gets big. $\endgroup$
    – Carl
    Dec 27 '12 at 2:28
  • 2
    $\begingroup$ There should be an easy way to show that $$\frac{e(n+1;G)}{{n+1\choose 2}}\leq \frac{e(n;G)}{{n\choose 2}},$$ in which case $e(n;G)/{n\choose 2}$ is monotone and nonnegative, and therefore convergent. We could see this by noting that with the addition of $1$ new vertex, $K_n$ gains $n$ edges while the extremal $G$-free graph gains fewer than $n$ edges. In particular, since $e(n;G)/{n\choose 2}$ is the probability of an edge in the extremal graph around that value of $n$, the number of edges added should be $\leq e(n;G)/{n\choose 2}\times n$ in the numerator. But this needs a better proof. $\endgroup$
    – Alexander Gruber
    Dec 27 '12 at 4:07
  • $\begingroup$ Well, I managed to reduce to the connected case but I think my method hit a wall there. Alexander's strategy seems right. $\endgroup$
    – Carl
    Dec 27 '12 at 21:53
  • $\begingroup$ I tried to prove @AlexanderGruber 's claim. Let's say $ex(n,G)/\binom n 2=a$. Inside the complete graph $K_{n+1}$, let strictly more than a proportion of $a$ edges be painted red, and the rest uncoloured. If this implies that in some sub-$K_n$, strictly more than a proportion of $a$ edges are red, then I have a red $G$. Thinking about it physically, along the lines of mass, density ..., if the "red density" in $K_{n+1}$ exceeds $a$, then I am likely to see this excess in some sub$K_n$. But let's assume not (for hopefully a contradiction). Take a vertex in $K_{n+1}$, remove it, and ... $\endgroup$
    – Spook
    Dec 29 '12 at 16:40

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

  • $\begingroup$ This is a much more concise argument. (By the way, I think that it should be "...such that $e$ is an edge of $H$ and $v$ is a vertex of $H$ not incident with $e$.") $\endgroup$ Nov 11 '13 at 14:42
  • $\begingroup$ Thanks for the correction. Yes, I mixed up $G$ and $H$. Too bad comments can't be edited. $\endgroup$
    – bof
    Nov 11 '13 at 15:07

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.

  • 2
    $\begingroup$ This doesn't answer the question at all. $\endgroup$
    – Antimony
    Dec 27 '12 at 8:18
  • $\begingroup$ @Antimony (1) Yes it does. (2) Instead of sass how would you suggest I improve it? $\endgroup$ Dec 27 '12 at 20:26
  • 2
    $\begingroup$ You did not show that the limit exists $\endgroup$
    – Amr
    Dec 28 '12 at 11:15

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.