= Solution
Let $X$ count copies of the <complete graph> $K_4$ in $G$. Its <expected value> is
$$
\mu=\mathbb EX=\binom n4p^6
\sim\frac{(\log n)^6}{24}\longrightarrow\infty.
$$
Write $X$ as a sum of <indicator random variables>[indicator random variable]. Indicators for two distinct copies are independent when the copies share at most one vertex, since their edge sets are then disjoint. Pairs sharing two vertices have eleven edges in their union, while pairs sharing three have nine. It follows that
$$
\operatorname{var}(X)
\leq \mu+O(n^6p^{11})+O(n^5p^9)
=O((\log n)^6)+o(1).
$$
\b[Thus $\operatorname{var}(X)/\mu^2\to0$. By the <second moment method>, $X/\mu\to1$ in probability, so $\mathbb P(X\geq100)\to1$. This is the <sparse clique-count concentration> estimate.]
Back to article page
