Graphs: Expected Number of Triangles and Variance

[jgens]

Homework Statement

Let $G$ be a random graph on $n$ vertices:
1) What is the expected number of triangles in $G$?
2) What is the variance in the number of triangles?

Homework Equations

N/A

The Attempt at a Solution

I think I can do (1) by using indicator variables. In particular, let $X$ denote the number of triangles in $G$, suppose $\theta_{ijk}$ is the indicator variable that the triple of vertices $i,j,k$ make a triangle, and let $A_{ijk}$ denote the event that the triple of vertices make a triangle. Then, we know
$$E(X) = \sum_{i,j,k}P(A_{ijk})$$
where the sum extends over all triples $i,j,k$. Since there are $\binom{n}{3}$ such triples and since $P(A_{ijk}) = \frac{1}{8}$, this means
$$E(X) = \binom{n}{3}\frac{1}{8}$$
which gives us the expected number of triangles.

Now, I just need help getting started with the variance problem. I think I'm just supposed to utilize the fact that $Var(X) = E(X^2) - E(X)^2$, but I'm not sure. Any help is appreciated.

 

[mighty2000]

Hi there! Your approach to the expected number of triangles is correct. For the variance, you are on the right track. You can use the formula Var(X) = E(X^2) - E(X)^2, but you will need to calculate E(X^2) as well.

To do this, you can use the same indicator variable approach. Let Y denote the number of pairs of vertices that share an edge. Then we can express X^2 in terms of Y as follows:
X^2 = \sum_{i,j,k} \theta_{ijk} \theta_{ijl}
where l is some vertex that is different from i,j,k. This is because for each triple (i,j,k) that forms a triangle, there are \binom{n-3}{1} ways to choose the fourth vertex l that will form a pair with one of the vertices in the triangle.

Now, we can use linearity of expectation to express E(X^2) in terms of E(Y):
E(X^2) = \sum_{i,j,k} E(\theta_{ijk} \theta_{ijl})
= \sum_{i,j,k} P(A_{ijk} \cap A_{ijl})
= \sum_{i,j,k} P(A_{ijk})P(A_{ijl}) (since the events are independent)
= \binom{n}{3} \frac{1}{8} \binom{n-3}{1} \frac{1}{8} (since P(A_{ijk}) = P(A_{ijl}) = \frac{1}{8})
= \binom{n}{3} \binom{n-3}{1} \frac{1}{64}

Finally, we can plug this into the formula for variance:
Var(X) = E(X^2) - E(X)^2
= \binom{n}{3} \binom{n-3}{1} \frac{1}{64} - (\binom{n}{3} \frac{1}{8})^2
= \binom{n}{3} \frac{(n-3)}{64} - \binom{n}{6} \frac{1}{64}
= \frac{n^3 - 6n^2 + 11n - 6}{384}

I hope this helps! Let me know if you have any further questions.