1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ $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 :) $\endgroup$ Mar 13, 2021 at 23:08

1 Answer 1

1
$\begingroup$

I think this is right...

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

Some examples:

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

$\endgroup$
2
  • $\begingroup$ Just to clarify: in your first example, did you mean to write $\binom{n}{k}(1/2)^{k(k-1)/2}$? $\endgroup$
    – sosgraf
    Mar 13, 2021 at 10:10
  • $\begingroup$ @sosgraf indeed I did! $\endgroup$ Mar 13, 2021 at 15:33

You must log in to answer this question.

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