Past exam of the mathematics course of the University of Cambridge / 2024 / ia / Paper 2 / 12F (Probability)

The degree of $v_i$ counts the $n-1$ incident edges, each present independently with probability $p$. Thus in the Erdős-Rényi model,

Let $I_i$ indicate that $v_i$ is isolated. All its $n-1$ incident edges must be absent, soSince $N={\sum }_{i=1}^n{I}_i$, linearity of expectation gives

With $p=c\log n/n$, the inequality $1-p\le e^{-p}$ giveswhen $c>1$. The Markov inequality now givesConsequently the upper side of the isolated-vertex threshold in the Erdős-Rényi model is

If $N=0$, then $|N-\mathbb{E}N|=\mathbb{E}N$. Hence the Chebyshev inequality givesThe assumed limit therefore provesThis is the second moment method in its simplest form.

Write $N={\sum }_i{I}_i$ as in part (ii). For $i\ne j$, the two vertices are both isolated exactly when their combined $2n-3$ incident edges are absent, soThereforeLet $A=\mathbb{E}N=n(1-p{)}^{n-1}$. The displayed formula gives

Now take $p=c\log n/n$ with $c<1$, and choose $\alpha >1$ such that $\alpha c<1$. For all sufficiently large $n$, the supplied inequality gives $1-p\ge e^{-\alpha p}$, whenceAlso $p\to 0$, so both terms in the variance ratio tend to zero. Part (iv) now applies and proves the lower side of the isolated-vertex threshold: