Expected subgraph count in the Erdős-Rényi model

If a fixed graph $H$ has $v$ vertices, $e$ edges, and $N_H(n)$ unlabelled copies in $K_n$, then the number $X_H$ of its copies in $G(n,p)$ satisfiesThis follows by writing $X_H$ as a sum of indicator random variables.

For $p=n^{-2/3}\log n$, the number $X$ of copies of $K_4$ satisfiesand $\mathrm{var}(X)=o((\mathbb{E}X{)}^2)$. Two distinct copies have dependent indicators only when they share at least two vertices; pairs sharing two or three vertices contribute respectively $O(n^6{p}^{11})$ and $O(n^5{p}^9)$ to the variance.

If $H$ is formed by attaching one pendant edge to a fixed clique, each copy has a unique clique core. Its number of extensions is the number of ambient edges from that core to outside vertices. At a scale where the core count is tight and its expected extension count diverges sufficiently rapidly, a Chernoff bound uniformly over all possible cores shows that the total count, divided by the extension mean, has the same limiting law as the core count. Non-induced copies are intended; extra ambient edges are not forbidden.

For $p=n^{-2/3}\log n$, the expected number of pairs of $K_4$ copies sharing a vertex isThus, with probability tending to one, all the $K_4$ copies are vertex-disjoint. Together with sparse clique-count concentration, this gives arbitrarily many vertex-disjoint copies with probability tending to one.