Problem: Let $H = P_3$, the path on 3 vertices. Prove that $n^{−3/2}$ is a threshold function for $G(n, p)$ to contain H as a subgraph.
My "proof":
Let $X=$ # of paths on three vertices.
Let $P_1,P_2,…P_k$ be the edge sets of all possible paths on three vertices, let $A_i$ be the event that $P_i \subset E(G)$, and let $X_i$ be the indicator function of $A_i$.
Then $X=\sum_{i=1}^{k}X_i$. Set $k = {n\choose 3}$.
Then $P[X_i] = p^2$ and $E[X] = kp^2 = {n\choose 3}p^2 \approx \frac{n^3p^2}{6}$.
Then we want to find a bound on,
$$Var[X] = \sum_{i} Var[X_i] + \sum_{i \neq j} Cov[X_i, X_j]$$
Let us bound each piece separately.
$$Var[X_i] = E[X_i^2]-E[X_i]^2 = E[X_i] – E[X_i]^2 = p^2 – p^4 \leq p^2$$
If $P_i \cap P_j = \emptyset$ then $A_i, A_j$ are independent, meaning $Cov[X_i,X_j] = 0$.
If $P_i \cap P_j \neq \emptyset$ then
$$Cov[X_i,X_j] = E[X_iX_j] – E[X_i]E[X_j] = ???$$
Giving,
$$Var[X] = \sum_{i} Var[X_i] + \sum_{i \neq j} Cov[X_i, X_j] \leq {n\choose 3}p^2 + ??? \leq n^3p^2 + ???$$
Now, apply Chebyshev's Inequality, with $t = E[X]$.
$$P[X=0] \leq P[|X-E[X]| \geq E[X]] \leq \frac{Var[X]}{E[X]^2}
\leq \frac{n^3p^2 + ?}{n^6p^4/36} = 36(n^{-3}p^{-2} + ???)$$
If $n^{-3/2}=o(p)$, then
$$n^{-3}p^{-2} = (n^{-3/2})^{2}p^{-2} = o(p^2)p^{-2} = o(1)$$
Is this at least the right idea? I feel that there are plenty of details that aren't quite right. And I am not sure how to compute covariance when the random variables are not independent, because there are multiple edges the paths can share. Any help would be appreciated!
I want to conclude that if $n^{-3/2} >> p$ then G has a path on three vertices.
If $n^{-3/2} << p$ then G does not have a path on three vertices.
Also, I don't want to just use that theorem (I can't recall the name) that gives threshold functions. I want to actually show in detail that for this specific situation the threshold function is $n^{-3/2}$.
Best Answer
The covariance computation is key to applying Chebyshev's inequality; it can't be left out as a minor detail. In the case of any sum of indicator variables $X_1, X_2, \dots, X_k$, you'll have $$\mathbb E[X^2] = \mathbb E[X] + 2\sum_{i=1}^k \sum_{j=1}^{i-1} \mathbb E[X_i X_j].$$ If we want to prove the upper half of a threshold, we are in a case where $\mathbb E[X] \to \infty$, and we want to show that $\mathbb E[X^2] = (1 + o(1)) \mathbb E[X]^2$. In this case, we'll always have $\mathbb E[X] \ll \mathbb E[X^2]$, so the contribution of the diagonal terms is insignificant. It's the second sum, where $\mathbb E[X_i X_j]$ appears, that we'll worry about.
To analyze $\mathbb E[X_i X_j]$, we consider two cases.
It's important to count the cases of the second type. In those cases, the union of the two paths forms either a $P_4$ subgraph (in which there are $2$ ways to pick the two paths) or a $K_{1,3}$ subgraph (in which case there are $6$ ways to pick the two paths). Some counting tells us that there are $6 \binom n4$ potential $P_4$ subgraphs and $4 \binom n4$ potential $K_{1,3}$ subgraphs. So there are $6 \binom n4 \cdot 2 + 4 \binom n4 \cdot 6 < \frac32 n^4$ cases of the second type.
For cases of the first type, it's enough to say that there are fewer than $k^2$ cases (because there are $k^2$ cases of any type). Most pairs of paths will have the first type, so we don't need to be too careful there.
So we get $$ \mathbb E[X^2] \le \underbrace{3 p^2 \binom n2}_{\text{diagonal terms}} + \underbrace{p^4 k^2}_{\text{first type}} + \underbrace{\frac32 n^4 p^3}_{\text{second type}}. $$ Meanwhile, $\mathbb E[X]^2 = p^4 k^2$, which neatly cancels the second term. So $\operatorname{Var}[X] \le 3 p^2 \binom n2 + \frac32 p^3 n^4$ and now you should be able to apply Chebyshev's inequality.
(This is the part that tells us that when $p \gg n^{-3/2}$, we have $X > 0$ w.h.p. Meanwhile, to prove that $X = 0$ w.h.p. when $p \ll n^{-3/2}$, showing that $\mathbb E[X] \to 0$ is enough.)