# Computing expected number of induced subgraphs of $G(n,\frac12)$ without graph removal lemma.

Define $$G(n,\frac12)$$ to be a graph on $$n$$ vertices where each edge has a $$\frac12$$ probability of being formed. We may compute the number of subgraphs of $$G(n,\frac12)$$ isomorphic to, say, $$K_3$$ as follows.

$$K_n$$ has $$\binom{n}{3}$$ such subgraphs; we can enumerate them as $$H_1,\cdots, H_{\binom{n}{3}}$$ and define $$X_i=\begin{cases} 1 & H_i\subseteq G(n,\frac12) \\ 0 & \text{otherwise}\end{cases}$$ to obtain $$\mathbb{E}[X] = \sum_i \mathbb{E}[X_i] = \binom{n}{3}\left(\frac12\right)^3$$.

But how can we count the number of induced subgraphs isomorphic to $$K_3$$?

It appears that the graph removal lemma gives me what I want for very special cases, but it is beyond the scope of my graph theory course. Surely there has to be a simpler approach when we are interested in "simple" subgraphs like $$P_n$$, $$C_n$$, or $$K_n$$.

• $K_3$ might not be the best example for what is generally an interesting question, because all copies of $K_3$ in a graph are induced :) Mar 13, 2021 at 23:08

For any smaller graph $$H$$, with $$k$$ vertices and $$e$$ edges, \begin{align} \mathbb E[\text{# subgraphs \cong H}] &=\binom{n}k\frac{k!}{|\operatorname{Aut}(H)|}(1/2)^{e} \\ \mathbb E[\text{# induced subgraphs \cong H}] &=\binom{n}k\frac{k!}{|\operatorname{Aut}(H)|}(1/2)^{k(k-1)/2} \end{align} $$\binom{n}k\frac{k!}{|\operatorname{Aut}(H)|}$$ counts the number places $$H$$ can appear in $$G$$; you choose the vertices, given them names, and note that two re-namings which result in the same $$H$$ should not be counted twice. The only difference is that having an induced subgraph requires the edges not present in $$H$$ to not be present in $$G$$ as well, leading to extra factors of $$1/2$$.
• If $$H$$ is a complete graph, then $$|\operatorname{Aut}(H)|=k!$$, so you get $$\binom{n}{k}(1/2)^{k(k-1)/2}$$ in either case.
• If $$H$$ is a cycle, then $$|\operatorname{Aut}(H)|=(k-1)!$$ so you get either $$\binom{n}{k}\cdot k(1/2)^{n}$$ subgraphs, and $$\binom{n}{k}\cdot k(1/2)^{n(n-1)/2}$$ induced subgraphs, on average.
• Just to clarify: in your first example, did you mean to write $\binom{n}{k}(1/2)^{k(k-1)/2}$? Mar 13, 2021 at 10:10