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?

$\endgroup$
6
  • $\begingroup$ Its a nice question $\endgroup$
    – Amr
    Dec 26, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 16:40

3 Answers 3

2
$\begingroup$

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

$\endgroup$
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, 2013 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, 2013 at 15:07
1
$\begingroup$

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

$\endgroup$
-3
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .