OurBigBook.comSite Source code

Triangle count in a binomial random graph

If

X

counts triangles in

G (n, p)

, then

E X = (3 n) p^{3}

and

var X \leq (3 n) p^{3} + 2 (2 n) (2 n - 2) p^{5} .

Thus

n p \to \infty

implies

var X / (E X)^{2} \to 0

, and the second moment method gives

P (X > 0) \to 1

.

 Ancestors (6)

 Incoming links (1)

Solution