Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / B (Probabilistic Combinatorics)

For a nonnegative random variable $Y$ and $a>0$, Markov inequality statesFor a random variable $X$ of finite mean $\mu$ and variance ${\sigma }^2$, Chebyshev inequality states that for every $t>0$,To prove it, apply Markov inequality to the nonnegative variable $(X-\mu {)}^2$ at threshold $t^2$:

For an indicator $I_i$, $\mathrm{Var}(I_i)=P(A_i)(1-P(A_i))\le P(A_i)$. Covariances vanish for independent pairs. For dependent distinct pairs,Expanding the variance, with ordered pairs as in the definition of $\Delta$, givesFor sufficiently large $n$, ${\mu }_n>0$. By Chebyshev inequality,This is the second moment method: a vanishing relative variance makes a zero count unlikely.

A threshold function $p^{\ast }(n)$ has the following meaning: if $p/p^{\ast }\to 0$, the probability of a $K_5$ tends to zero; if $p/p^{\ast }\to \infty$, that probability tends to one. Behavior at a fixed constant multiple is not specified by this definition.

Let $X$ count the five-vertex subsets spanning $K_5$ in the Erdős-Rényi model $G(n,p)$. ThenIf $p\ll n^{-1/2}$, then $\mu \to 0$, so Markov inequality gives $P(X>0)\le \mu \to 0$.

Now let $p=n^{-1/2}w$ with $w\to \infty$. Then $\mu \sim w^{10}/120\to \infty$. Distinct copies have dependent indicators only if their vertex sets share at least two vertices. If they share $j\in \{2,3,4\}$ vertices, they share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges; there are $O(n^{10-j})$ ordered such pairs, and their joint probability is $p^{20-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. ConsequentlyPart (b) gives $P(X=0)\to 0$. ThereforeThis is the five-vertex instance of the fixed-size clique appearance threshold.

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.

First take $0<p<1$. For $X\sim \mathrm{Bin}(n,p)$, independence of the Bernoulli trials givesFor $x\ge p$ and $t>0$, Markov inequality yieldsDifferentiate the logarithm of the right-hand side to minimize it. The stationary point satisfieswhich is at least $1$ when $x\ge p$. Substitution givesWhen $x=p$, use the limit $t_{\ast }\to 0$, giving the trivial bound $1$.

For $x\le p$, take $t<0$. On $\{X\le nx\}$ we have $e^{tX}\ge e^{tnx}$, so the same Markov inequality gives the same expression. Its minimizing $t_{\ast }$ is now nonpositive, yielding the stated lower-tail bound. No rounding of $nx$ is needed, because the exponential event inclusion holds for real thresholds. The cases $p=0$ and $p=1$ are deterministic and follow directly, or by the corresponding limits.

Write the bound in part (a) as $e^{-nD(x\Vert p)}$, where the Bernoulli Kullback-Leibler divergence with natural logarithms isFor fixed $p\in (0,1)$, $D(p\Vert p)=0$, its first derivative with respect to $x$ vanishes at $p$, andIntegrating this lower bound twice, on either side of $p$, gives the Bernoulli relative entropy lower bound $D(x\Vert p)\ge 2(x-p{)}^2$. Apply the two tails from part (a) at $x=p+h$ and $x=p-h$ and use the union bound:A tail with threshold outside $[0,1]$ is empty; thresholds at the endpoints follow by continuity of the bound. For $h=0$ the right-hand side is $2$, so the assertion is immediate. This is the binomial form of Hoeffding inequality.

The sum of the first $n/2$ variables has distribution $\mathrm{Bin}(n/2,1/2)$. For any fixed half-circle interval $I$, putThe $n$ terms defining $Z_I$ are independent Bernoulli variables of parameter $1/2$, so $Z_I\sim \mathrm{Bin}(n,1/2)$ and $D_I=Z_I-n/2$. Part (b), with $h=w/n$, givesThere are at most $n$ cyclic intervals of length $n/2$; this also covers the non-wrapping interpretation in the question. They need not be independent, since the union bound always applies. HenceWith $w=c\sqrt{n\log n}$ and natural logarithms, this becomes $2n^{1-2c^2}$, which tends to zero for every $c>1/\sqrt{2}$. In particular,The argument proves uniform half-circle balance for independent Bernoulli variables. It improves on separately bounding the two half sums by recognizing the difference as one centered binomial variable.