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

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.

Expand $X^2={\sum }_{A,B}{I}_A{I}_B$, where the sum is over ordered pairs of $k$-sets. If $|A\cap B|=l$, the two cliques together require $2\left(\genfrac{}{}{0ex}{}{k}{2}\right)-\left(\genfrac{}{}{0ex}{}{l}{2}\right)$ different edges: precisely the edges within the overlap are counted twice. ThereforeThere are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ choices of $A$, then $\left(\genfrac{}{}{0ex}{}{k}{l}\right)$ ways to choose the overlap and $\left(\genfrac{}{}{0ex}{}{n-k}{k-l}\right)$ ways to choose the remaining vertices of $B$. It follows thatA binomial coefficient is zero when its lower argument is outside its possible range. The term $l=k$ includes $A=B$ and equals $\mathbb{E}X$, as it should.

Now take the usual fixed-$k$ interpretation of the appearance assertion. For $k=1$, $X=n$ deterministically. For fixed $k\ge 2$, the assumption ${\mu }_n\to \infty$ givessince ${\mu }_n\sim a_n^k/k!$. Eventually $p>0$. Subtracting ${\mu }_n^2$ in the second-moment formula, and using the identity that the overlap counts sum to the total number of ordered pairs, gives the overlap formula for the variance of a clique count:Overlaps of zero or one vertex have no shared edge and hence independent indicators, so their contributions vanish. For fixed $k$, the combinatorial coefficient in the $l$-th summand is $O_k(n^{-l})$. Moreover, because $p\le 1$ and $l\le k$,There are only finitely many terms. Thus $\mathrm{Var}X/{\mu }_n^2\to 0$. The Chebyshev inequality then givesproving the fixed-size clique appearance threshold:

The fixed-size condition cannot simply be dropped. For $k=n-1$ and $p=1-(\log n)/n^2$,However the complement graph has a binomial number $J$ of missing edges with mean asymptotic to $\frac{1}{2}\log n$ and variance at most that mean. By the Chebyshev inequality, $\mathbb{P}(J\ge 2)\to 1$. Conditional on $J\ge 2$, choose two distinct missing edges uniformly; their endpoints are disjoint except with probabilityThus with probability tending to one the complement has two disjoint edges. Deleting one vertex cannot remove both, so no $(n-1)$-clique exists. In this example $\mathbb{P}(X\ge 1)\to 0$, despite ${\mu }_n\to \infty$. This is growing clique size can invalidate a first-moment appearance criterion; the exact second-moment identity remains valid for growing $k$, but the stated conclusion needs the conventional fixed-$k$ quantifier.