Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 37 / 2 / 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 $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ required edges are independent, soThe Markov inequality, or first moment method, givesConsequentlyThis 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.