- #1

jgens

Gold Member

- 1,581

- 50

## Homework Statement

Let [itex]G[/itex] be a random graph on [itex]n[/itex] vertices:

1) What is the expected number of triangles in [itex]G[/itex]?

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 [itex]X[/itex] denote the number of triangles in [itex]G[/itex], suppose [itex]\theta_{ijk}[/itex] is the indicator variable that the triple of vertices [itex]i,j,k[/itex] make a triangle, and let [itex]A_{ijk}[/itex] denote the event that the triple of vertices make a triangle. Then, we know

[tex]E(X) = \sum_{i,j,k}P(A_{ijk})[/tex]

where the sum extends over all triples [itex]i,j,k[/itex]. Since there are [itex]\binom{n}{3}[/itex] such triples and since [itex]P(A_{ijk}) = \frac{1}{8}[/itex], this means

[tex]E(X) = \binom{n}{3}\frac{1}{8}[/tex]

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 [itex]Var(X) = E(X^2) - E(X)^2[/itex], but I'm not sure. Any help is appreciated.