Graph convergence on probability Good afternoon.
In one book on probability theory I came across this problem which I found myself difficult to understand and prove. Would appreciate any help on that:
Let $X_n$ be the number of complete subgraphs on 4 vertices in $G(n,\frac{1}{2})$. Prove that $\frac{X_n-E(X_n)}{E(X_n)} \xrightarrow{P} 0$
 A: Let $Z_n=(X_n-\mathsf{E}X_n)/\mathsf{E}X_n$. Then for each $\epsilon>0$,
$$
\mathsf{P}(|Z_n|\ge \epsilon)\le \epsilon^{-2}\operatorname{Var}(Z_n)=\frac{\operatorname{Var}(X_n)}{\epsilon^2(\mathsf{E}X_n)^2}.
$$
It suffices to show that the last term converges to $0$ as $n\to\infty$.
First, since the probability that a given set of $r$ nodes is a complete subgraph is $p^{\binom{r}{2}}$ (where $p$ denotes the connectivity parameter; $p=1/2$ in your case),
$$
\mathsf{E}X_n=\binom{n}{r}p^{\binom{r}{2}}.
$$
Second, since one can choose $\binom{n}{r}\binom{r}{i}\binom{n-r}{r-i}$ ordered pairs of sets of $r$ nodes with $i$ nodes in common,
$$
\mathsf{E}X_n^2=\sum_{i=0}^r\binom{n}{r}\binom{r}{i}\binom{n-r}{r-i}p^{2\binom{r}{2}-\binom{i}{2}}
$$
because the probability of two complete subgraphs of $r$ nodes with $i$ nodes in common is  $p^{2\binom{r}{2}-\binom{i}{2}}$ (we assume that $n\ge 2r$).
Finally, it is easy to show that
$$
\frac{\operatorname{Var}(X_n)}{(\mathsf{E}X_n)^2}=\binom{n}{r}^{-1}\sum_{i=2}^r\binom{r}{i}\binom{n-r}{r-i}\left(p^{-\binom{i}{2}}-1\right).
$$

Plugging $r=4$ and $p=1/2$, we get
$$
\frac{\operatorname{Var}(X_n)}{(\mathsf{E}X_n)^2}=\left(6\binom{n-4}{2}+28n-49\right)\binom{n}{4}^{-1}\to 0
$$
as $n\to\infty$.
