= Solution
Let $X$ count the four-vertex sets spanning a <clique>. Its expectation is $\mu=\binom n4p^6$. If $p\ll n^{-2/3}$, then $\mu\to0$ and <Markov's inequality> gives $P(X>0)\to0$.
Now suppose $p\gg n^{-2/3}$. Then $\mu\to\infty$. Two distinct <clique> indicators are independent unless their vertex sets share at least two vertices. An overlap of two vertices gives $O(n^6)$ ordered pairs requiring eleven distinct edges; an overlap of three gives $O(n^5)$ pairs requiring nine edges. Consequently
$$
D=O(n^6p^{11}+n^5p^9),\qquad
\frac D{\mu^2}=O(n^{-2}p^{-1}+n^{-3}p^{-3})\longrightarrow0.
$$
The preceding second-moment bound therefore gives $P(X=0)\to0$. Thus
$$
\boxed{p_*(n)=n^{-2/3}}
$$
is a threshold for the appearance of a four-<clique>. Sharing just one vertex creates no dependence because the two edge sets are disjoint.
Back to article page
