Graphs: Expected Number of Triangles and Variance

  • Thread starter jgens
  • Start date
  • #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.
 

Answers and Replies

Related Threads on Graphs: Expected Number of Triangles and Variance

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
0
Views
2K
Replies
6
Views
919
  • Last Post
Replies
1
Views
1K
Replies
6
Views
3K
Replies
3
Views
897
Replies
4
Views
4K
  • Last Post
Replies
1
Views
2K
Replies
5
Views
3K
Top