Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / B / 5 / Solution

Start the Galton-Watson process with one ancestor, $Z_0=1$, and let every individual independently have a number of offspring distributed as $Z$. With independent copies $Z_{t,j}$,where an empty sum is zero. Extinction is the event that some generation is empty; zero is then absorbing. Write $q$ for its probability and $1-q$ for the survival probability.

Set $q_t=P(Z_t=0)$, with $q_0=0$. Conditional on the ancestor's number of children, extinction by generation $t+1$ requires independent extinction by generation $t$ in every child subtree. ThusThe events $\{Z_t=0\}$ increase, so $q_t\uparrow q$. The probability generating function is continuous on $[0,1]$, by domination of $s^Z$ by $1$, giving $q=f_Z(q)$. If $r\in [0,1]$ is any fixed point, then $q_0=0\le r$ and monotonicity of $f_Z$ inductively gives $q_t\le r$. Taking limits proves the Galton-Watson extinction fixed point characterization:In particular it is the smallest nonnegative fixed point wherever the generating series is defined, since it already lies in $[0,1]$.

Let $m=\mathbb{E}Z=f_Z^{\prime }(1-)$, allowing $m=\infty$. The probability generating function is increasing and convex, with $f_Z(1)=1$. If $m<1$, its tangent inequality gives $f_Z(s)\ge 1+m(s-1)>s$ for $s<1$, so $q=1$. If $m=1$ and $P(Z=1)\ne 1$, there is positive mass at both zero and some integer at least two; strict convexity gives $f_Z(s)>s$ for $s<1$, again $q=1$. The exceptional case $Z=1$ almost surely has one individual forever, so $q=0$ despite $m=1$.

If $m>1$, the left derivative at $1$ gives $f_Z(s)-s<0$ for $s<1$ sufficiently close to $1$. Since $f_Z(0)\ge 0$, continuity supplies a fixed point below $1$, possibly $0$. Thus survival has positive probability precisely when $m>1$, apart from deterministic one-child reproduction.

For the random bipartite graph, early exploration of a component alternates between the two vertex classes. Before many vertices are exposed, each discovered vertex has approximately $\mathrm{Poisson}(c)$ new neighbors in the other class, since $\mathrm{Bin}(n-O(1),c/n)$ tends to that distribution. The two-type mean offspring matrix iswith spectral radius $c$; equivalently, the mean growth over two generations is $c^2$. The branching-process comparison therefore predicts a giant component exactly whenFor $c\le 1$, the local process dies out almost surely, so no linear-sized component is expected; $c=1$ is the critical case, not a positive-survival exception. For $c>1$, the symmetric survival probability is $1-q>0$, where $q=e^{c(q-1)}$, predicting approximately $2n(1-q)$ vertices in the giant. This last passage from local survival to a unique giant is the usual random-graph exploration argument; the branching-process reasoning here supplies the requested threshold explanation rather than a proof of that global theorem.