= Solution
A <threshold function for a monotone graph property>[threshold function] $p^*(n)$ has the following meaning: if $p/p^*\to0$, the <probability> of a $K_5$ tends to zero; if $p/p^*\to\infty$, that <probability> tends to one. Behavior at a fixed constant multiple is not specified by this definition.
Let $X$ count the five-<vertex> subsets spanning $K_5$ in the <Erdős-Rényi model> $G(n,p)$. Then
$$
\mu=\mathbb EX=\binom n5p^{10}.
$$
If $p\ll n^{-1/2}$, then $\mu\to0$, so <Markov inequality> gives $P(X>0)\leq\mu\to0$.
Now let $p=n^{-1/2}w$ with $w\to\infty$. Then $\mu\sim w^{10}/120\to\infty$. Distinct copies have dependent indicators only if their <vertex> sets share at least two vertices. If they share $j\in\{2,3,4\}$ vertices, they share $\binom j2$ edges; there are $O(n^{10-j})$ ordered such pairs, and their joint <probability> is $p^{20-\binom j2}$. Consequently
$$
\frac\Delta{\mu^2}
=O\left(\frac1{n^2p}+\frac1{n^3p^3}+\frac1{n^4p^6}\right)
=O\left(\frac1{n^{3/2}w}+\frac1{n^{3/2}w^3}+\frac1{nw^6}\right)\longrightarrow0.
$$
Part (b) gives $P(X=0)\to0$. Therefore
$$
\boxed{p^*(n)=n^{-1/2}.}
$$
This is the five-<vertex> instance of the <fixed-size clique appearance threshold>.
Back to article page
