Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 36 / 3 / b / i / Solution

Count each unordered triple once. For a three-element vertex set

S

, let

I_{S}

indicate that its three edges are present. Then

X = \sum_{∣ S ∣ = 3} I_{S}

and

E X^{2} = \sum_{S, T} E [I_{S} I_{T}] .

If

∣ S \cap T ∣ = ℓ

, their edge sets have

(2 ℓ)

edges in common, so their union contains

6 - (2 ℓ)

distinct edges. Independence gives

E [I_{S} I_{T}] = p^{6 - (2 ℓ)}

. There are

(3 n) (ℓ 3) (3 - ℓ n - 3)

such ordered pairs: choose

S

, its shared vertices, and the remaining vertices of

T

. Thus

E X^{2} = (3 n) ℓ = 0 \sum 3 (ℓ 3) (3 - ℓ n - 3) p^{6 - (2 ℓ)} .

This overlap count is the basis of triangle variance in a binomial random graph.

 Ancestors (12)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version