Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-14/4/a/solution
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 14 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let be the number of isolated vertices and set . For fixed , the falling factorial counts ordered -tuples of distinct isolated vertices. A specified tuple is isolated exactly when all edges incident to its vertices are absent. There are such edges, soSince and , taking logarithms givesThus every fixed factorial moment tends to . We use the standard factorial-moment criterion for Poisson convergence: nonnegative integer-valued random variables whose factorial moments converge, for every fixed order, to converge in distribution to . Consequently 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.
New to topics? Read the docs here!