Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 14 / 4 / a

Let $Y$ be the number of isolated vertices and set $\lambda =e^{-c}$. For fixed $k\ge 1$, the falling factorial $(Y{)}_k$ counts ordered $k$-tuples of distinct isolated vertices. A specified tuple is isolated exactly when all edges incident to its vertices are absent. There are $k(n-k)+\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ such edges, soSince $np=\log n+c$ and $n{p}^2=o(1)$, taking logarithms givesThus every fixed factorial moment tends to ${\lambda }^k$. We use the standard factorial-moment criterion for Poisson convergence: nonnegative integer-valued random variables whose factorial moments converge, for every fixed order, to ${\lambda }^k$ converge in distribution to $\mathrm{Poisson}(\lambda )$. Consequently $Y$ has that limiting distribution, and its mass at each fixed integer converges. In particular,This establishes the limiting probability of at least one isolated vertex, rather than merely a bound based on its expectation.