# Probability of at least one triangle in Erdos-Renyi graph

This is a well-known problem in random graph theory, where we show that if $X$ is the number of triangles in $G(V,E,p)$ with $p=o(\frac{1}{n})$, we can show that $$P(X \geq 1) \geq 1-o(\frac{1}{n}) \to_n 1$$ using Chebyshev inequality and asymptotic expansion of binomial coefficients, $\binom{n}{k} \sim \frac{n^k}{k!}$.

What I don't understand is the part where the second moment is used for indicator variables: $$\mathbf{E}X^2 = \mathbf{E} (\sum_{k=1}^{\binom{n}{3}} X_k)^2 = \sum_{k=1}^{\binom{n}{3}} \mathbf{E}X^2_k +\sum_{k \neq j}\mathbf{E}X_k X_j$$ Specifically, I don't understand the absence of 2 in front of the second sum. The explanation is that triangles are ordered. This means that selecting triangle $X_j$ and then $X_k$ is different to $X_k$ and then $X_j$. Could someone explain why?

The issue seems to be just about understanding the notation in the summation index, that is, nothing to do with the specifics of the graph problem.

$\sum_{k\neq j}$ refers to summing over all $(k,j)$ with $k,j \in \{1,\ldots,n\}$ such that $k\neq j$. So, both $(i,l)$ and $(l,i)$ for any $i\neq l$. Since $\mathbb{E}X_k\,X_j = \mathbb{E}X_j\,X_k$, we have

$$\sum_{k\neq j} \mathbb{E}(X_k\,X_j) = 2\,\sum_{k<j} \mathbb{E}(X_k\,X_j),$$ where $\sum_{k<j}$ refers to all pairs of indices where $1\leq k < j \leq n$. You are probably thinking about this latter summation.

For example, when $n=2$, $\mathbb{E}((X_1+X_2)^2)$ can be expressed either as $$\mathbb{E}(X_1^2+X_1\,X_2+X_2\,X_1+X_2^2) = \mathbb{E}(X_1^2)+\mathbb{E}(X_2^2)+\mathbb{E}(X_1\,X_2)+\mathbb{E}(X_2\,X_1)$$ which is the notation appearing in the question unfolded. Or, since $X_1\,X_2=X_2\,X_1$, this is equal to $$=\mathbb{E}(X_1^2) + \mathbb{E}(X_2^2) + 2\,\mathbb{E}(X_1\,X_2)$$ which is the $\sum_{k<j}$ notation unfolded.

• I'm sorry i don't quite see how this answers my question. The source here:ndsu.edu/pubweb/~novozhil/Teaching/767%20Data/chapter_3.pdf: 'Here Here we assume that all possible triples are ordered and labeled.we assume that all possible triples are ordered and labeled.'. I understand the labelled part (hence $\binom{n}{3}$ number of choices, but why is it ordered? Like triangle 1 and 2 vs 2 and 1 are different. Why?
– Alex
Apr 3 '16 at 12:08
• Can you give a page number? See page 5, "Here the sum in the second term is taken through all the ordered pairs of $i\neq j$, hence there is no “2” in the expression." Apr 3 '16 at 12:25
• I maybe misunderstood your question, since I thought you are asking about why $E(\sum(X_i)^2) = \sum_i(E(X_i)^2) + \sum_{i\neq j}(X_i\,X_j)$ rather than $E(\sum(X_i)^2) = \sum_i(E(X_i)^2) + 2\, \sum_{i\neq j}(X_i\,X_j)$ Apr 3 '16 at 12:27
• You looked at Thm 3.4 and 3.5, this is exactly my problem. I don't understand why there's not 2 in front of this sum over $\mathbf{E} X_i X_j$ or, rewording it, why the triangles are ordered
– Alex
Apr 3 '16 at 12:36
• Please add a reference/link to the source into the question and clarify that you are asking about the proof of Thm 3.4 on page 5 (if you are asking about something else, clarify that...) Apr 3 '16 at 18:49