Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 3 / c / Solution

Write $f_n(q)=\mathbb{P}(G(n,q)\in P_n)$. This is increasing in $q$ by monotone coupling of binomial random graphs, and $f_n(p)=1/10$ by hypothesis.

First let $q/p\to 0$. Choose $k=\lfloor p/(2q)\rfloor$, so $k\to \infty$. The union of $k$ independent copies of $G(n,q)$ has distribution $G(n,q^{\prime })$, whereIf any layer has $P_n$, their union has $P_n$, and henceIt follows that $f_n(q)\le 1-(9/10{)}^{1/k}\to 0$.

Now let $q/p\to \infty$. Choose $k=\lfloor q/(2p)\rfloor$, again tending to infinity. The union of $k$ independent $G(n,p)$ graphs has parameterMonotonicity and independence giveThus $p(n)$ is a threshold function.