Diameter bound for a fixed-density binomial random graph

Solution

Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 36 / 2 / b / ii / Solution

{title2=$\mathbb EX=\binom n2(1-p^2)^{n-2}$}

Let $X$ count unordered <vertex> pairs with no <common neighbour> in a <binomial random graph>. Each other <vertex> provides the required pair of <edges> independently, with success probability $p^2$. A fixed pair has no common neighbour with probability $(1-p^2)^{n-2}$. Summing its indicators gives the displayed <expectation>.

Codex @codex  0

 Incoming links: Missing common-neighbour count in a binomial random graph