Recently, I am learning about the weak law of large numbers (WLLN) and I find some of its interesting applications on random graphs. The question is as follows.
Given $n$ vertices labelled by $\{ 1, 2, . . . , n \}$, independently for each unordered pair of vertices $\{ i, j\}$ with $1\leq i\neq j \leq n$, we draw an edge between $i$ and $j$ with a fixed probability $p\in (0,1)$. A set of three vertices $\{ i, j, k \}$ is said to form a triangle if there is an edge between every pair of vertices. Let $\Delta_{n}$ denote the number of triangles in the random graph defined above. We can write $ \Delta_{n} = \sum_{1\leq i<j<k\leq n} 1_{\{ i,j,k\ \textrm{form a triangle} \}}$. It is not hard to get $ \mathbb{E}(\Delta_{n})=\tbinom{n}{3}p^{3}$. Then try to prove: for any $\epsilon > 0$, we have $$P\left(\left|\frac{\Delta_{n}}{\mathbb{E}(\Delta_{n})}-1\right|>\epsilon\right) \to 0 \text{ as } n\to \infty$$
I found $1_{\{ i,j,k\ \rm{form\ a\ triangle}\}}$ is not an independent sequence. Then I don't know how to prove it. Is there anyone who can give me some hints or answers? Thank you very much.
By Chebychev's inequality, $$P(|\Delta_n - E[\Delta_n]| > \epsilon E[\Delta_n]) \le \frac{\text{Var}(\Delta_n)}{\epsilon^2 E[\Delta_n]^2}.$$
You know $E[\Delta_n]^2 = \binom{n}{3}^2 p^6$.
With some casework on covariance terms $\text{Cov}(1_{i,j,k}, 1_{i', j', k'})$, you can show (see here or here) that the variance is $$\text{Var}(\Delta_n) = 4\binom{n}{4} (p^5 - p^6) + \binom{n}{3}(p^3 - p^6).$$
With $p$ fixed and $n \to \infty$, we have $\frac{\text{Var}(\Delta_n)}{\epsilon^2 E[\Delta_n]^2} \to 0$ because the numerator grows as $n^4$ while the denominator grows as $n^6$.