Let $H$ be a graph. Prove that almost every graph $G \in \mathcal{G}_{n,p}$ has $H$ as an induced subgraph

Question

Let $H$ be a graph. Prove that almost every graph $G \in \mathcal{G}_{n,p}$ has $H$ as an induced subgraph.

Couldn't reach far on this one... My naive approach was to use Markov's inequality with the random variable: $$ X_n(G) = \cases{ 1, \text{if } G \text{ does not have } H \text{ as induced subgraph}\\ 0, \text{otherwise} } $$ Therefore, if I'm able to prove that $E(X_n) \rightarrow 0$ as $n \rightarrow \infty$ then Markov's inequality guarantees that $P(X_n=0) \rightarrow 1$, and that shows that almost every graph on $\mathcal{G}_{n,p}$ would have $H$ as an induced subgraph.

The problem with that approach is to actually show that $E(X_n) \rightarrow 0$. By definition we'd have:

$$ E(X_n) = \sum_{g \in \mathcal{G}_{n,p}} X_n(g)P(g) = \sum_{g \in (X_n=1)}p^{|E(g)|}(1-p)^{{n \choose 2}-|E(g)|} $$

And after that I tried to find a pattern on graphs that would not have $H$ as induced subgraph to partition the event set $X_n=1$ and properly calculate $E(X_n)$, but failed on this.

I might be misunderstanding the problem... Can someone please provide some guidance? Thanks!

Answer 1

The challenge with properly understanding the number of induced copies of $H$ in $\mathcal G_{n,p}$ is the high degree of dependence; there are way too many potential copies of $H$ that could appear, and they overlap in complicated ways.

However, the statement "with high probability, the number of induced copies of $H$ is not zero" is actually an incredibly weak claim about that number - so we can give away a lot of power, in exchange for simplicity, and still be able to prove it.

Let $H$ have $k$ vertices. Divide the vertex set of $\mathcal G_{n,p}$ into $\lfloor n/k\rfloor$ disjoint sets of $k$ vertices, and possibly a leftover part we don't care about. Then:

• Each of the $\lfloor n/k\rfloor$ sets has a nonzero probability $q$ of inducing a copy of $H$. (Note that $q$ does not depend on $n$; it is the probability that a random $k$-vertex graph is isomorphic to $H$.)
• These events are independent for different sets of $k$ vertices. So the probability that none of them induce a copy of $H$ is $(1-q)^{\lfloor n/k\rfloor}$.
• As $n \to \infty$, $\lfloor n/k\rfloor \to \infty$, so $(1-q)^{\lfloor n/k\rfloor} \to 0$.

For the sake of independence, we've ignored almost all potential copies of $H$ we could get, but just the few we have left are still enough to get the result we want.