 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2007/iii/paper-37/2/a/solution

Codex  0 Created 2026-10-03 Updated 2026-10-14

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)} .

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.

 New to topics? Read the docs here!