Show that $G_{n,p}$ does not contain a certain subgraph.

Question

LEMMA. Let $a=a(n), c=c(n)$ be functions of $n$ such that $a(n) \geq 1.1$ and $c(n)=$ $o\left(a n^{1-1 / a}\right) .$ Then, for $p(n)=c(n) / n, G(n, p)$ a.s. contains no subgraphs with $s$ vertices, $s \leq 0.35\left(\frac{2 a}{c}\right)^{a /(a-1)} \exp \left(-\frac{2}{a-1}\right) n$, and more than as edges.

I suppose this could be shown using the first moment method (i.e., $P(X > 0) \leq E(X)$). So I let $X$ be a random variable that counts the number of subgraphs of $G_{n,p}$ with $s$ vertices, and $as$ edges. Is the following the correct expression for $E(X)$?

$$E(X) = {n \choose s} {{s \choose 2} \choose as} p^{as}$$

Next I’d have to show $E(X) \to 0$, but I don’t know where to start.

Answer 1

What we want for $\mathbb E[X]$ is $$ \sum_{s=1}^{s_\max} \binom ns \Pr[s\text{-vertex subgraph has $\ge as$ edges}] $$ (where $s_\max$ is the upper bound $0.35\left(\frac{2 a}{c}\right)^{a /(a-1)} \exp \left(-\frac{2}{a-1}\right) n$).

A term like $\binom{\binom s2}{as} p^{as}$ is an upper bound for the probability, but it's giving a lot away. More precisely, $\binom{\binom s2}{as} p^{as} (1-p)^{\binom s2 - as}$ would be the probability of exactly $as$ edges, and the factor of $(1-p)^{\binom s2 - as}$ could be significant when $s$ is large. Dropping this factor means that other cases, where there are more than $as$ edges, also get counted - but actually, they get substantially overcounted.

In reality:

• If $as < p \binom s2$ (so that our threshold of $>as$ edges is below the expected number of edges in the subgraph) then the probability we want is between $\frac12$ and $1$. In this case, $\mathbb E[X]$ would not go to $0$, so we expect that the bounds we're given imply that $as > p\binom s2$.
• If $as > p \binom s2$, then the easiest thing to say is that "exactly $as$ edges" is the likeliest case out of all cases with "at least $as$ edges", so an upper bound on $\Pr[s\text{-vertex subgraph has $\ge as$ edges}]$ is $\color{red}{\binom s2 \cdot} \binom{\binom s2}{as} p^{as} (1-p)^{\binom s2 - as}$.
• Better yet, if it turns out that $as > 2 p \binom s2$ or so, then we're in a range where $\Pr[\text{exactly $k+1$ edges}] < \frac12 \Pr[\text{exactly $k$ edges}]$ for $k \ge as$, and so a geometric series bounds $\Pr[s\text{-vertex subgraph has $\ge as$ edges}]$ by $\color{red}{2 \cdot} \binom{\binom s2}{as} p^{as} (1-p)^{\binom s2 - as}$. We don't care about constants in $\mathbb E[X]$, so this is as good as it gets.
• Instead of dealing with the above nonsense, an alternative option is to use a Chernoff bound.

I haven't worked out the details of dealing with $\mathbb E[X]$ from here, so it's possible that the bound we want is weak enough that your expression, without $(1-p)^{\binom s2 - as}$, will also work. (You should still realize that it's an upper bound, not exact.)

You may need to split up the sum into several ranges of $s$, in which different parts of the analysis need to be done carefully.