Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 37 / 2 / a

Table of contents
- Solution a

Solution

Count each unordered

k

-vertex set once. For each such set

A

, let

I_{A}

be its clique indicator in the binomial random graph. All

(2 k)

required edges are independent, so

X = \sum_{∣ A ∣ = k} I_{A}, μ_{n} = E X = (k n) p^{(2 k)} .

The Markov inequality, or first moment method, gives

P (X \geq 1) \leq E X = μ_{n} .

Consequently

μ_{n} \to 0 ⟹ P (X = 0) \to 1.

This argument works even if

k = k (n)

varies. The binomial coefficient shows that cliques are counted as vertex sets, not as their different ordered listings.

 Ancestors (10)

 View article source

 Discussion (0)

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