$k\geq3$ , $np \rightarrow \infty$ show that w.h.p $G_{n,p}$ contains a copy of the k-cycle $Ck$

Question

I had been given this questions:

Suppose that $k\geq3$ is constant and that ($np \rightarrow \infty$). show that with high probability $G_{n,p}$ contains a copy of the k-cycle $Ck$

The questions is from the book 'Intro to random graphs', but theres no solution, and i have no clue..

Answer 1

Use the second moment method.

Let $X$ be the number of copies of $C_k$ in a random graph with distribution $G_{n,p}$. You want to show that $\mathbb{P}(X = 0) \to 0$ as $n \to \infty$.

Chebyshev's inequality implies that if $X$ is a nonnegative random variable with finite mean and nonzero variance, then $$\mathbb{P}(X = 0) \leq \mathbb{P}\bigl(|X - \mathbb{E}X| \geq \mathbb{E}(X)\bigr) \leq \frac{\operatorname{Var} X}{(\mathbb{E}X)^2}.$$

So, you want to show that $\operatorname{Var} X$ is much smaller than $(\mathbb{E}X)^2$.

N.B.: $\operatorname{Var} X = \mathbb{E}X^2 - (\mathbb{E}X)^2$. In this case, to compute $\mathbb{E}X^2$, it helps to compute the expected number of pairs of distinct copies of $C_k$, which is $\mathbb{E}X(X - 1) = \mathbb{E}X^2 - \mathbb{E}X$.