Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 9 (Percolation on Graphs)

Put $d=np=\gamma \log n$ and $\mu =n^{1-\gamma }$. The hypothesis implies $\mu \ge e^{\omega (n)}\to \infty$. For the number $I$ of isolated vertices, the isolated vertices in the Erdős-Rényi model formulas giveThus the Chebyshev inequality gives $I=(1+o(1))\mu$ with high probability, uniformly over the specified $\gamma$ range.

The Cayley formula supplies a spanning tree on any connected vertex set. Consequently the expected value $C_j$ of the number of graph components of order $j\ge 2$ is bounded byChoose a fixed $\eta \in (0,1/2)$ with ${\gamma }_0(1-\eta )(k+1)>1$. For $k+1\le j\le \eta n$, with $j\ge 2$, the binomial coefficient bound $\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le (en/j{)}^j$ givesHere $ed{e}^{-d(1-\eta )}\le e\log n{n}^{-{\gamma }_0(1-\eta )}\to 0$. The geometric series and a union bound therefore exclude this entire size range, since $n[e\log n{n}^{-{\gamma }_0(1-\eta )}{]}^{k+1}=o(1)$. For $\eta n\le j\le n/2$, an empty graph cut would be necessary. Its total probability is at mostThere are consequently no graph components of orders between $k+1$ and $n/2$, with high probability.

For each fixed $2\le j\le k$, a graph component containing a graph cycle has a spanning tree and at least one extra edge. Counting that extra edge gives an expected value $O_k(d^j{e}^{-dj})=o(1)$; hence every small graph component is a tree component. The total number $R_2$ of vertices in tree components of orders $2,\dots ,k$ satisfiesThe Markov inequality gives $R_2=o(\mu )$ with high probability. When $k=1$, this sum is empty and $R_2=0$. Since $\mu =o(n)$, the remaining vertices must lie in one graph component larger than $n/2$. It is unique, and its order is $n-(1+o(1))n^{1-\gamma }$. Every other graph component is a tree with at most $k$ vertices. This is the logarithmic-regime giant component mechanism: almost all missing vertices are isolated.

It suffices to prove the assertion after replacing $\omega$ by $\min \{\omega ,\sqrt{\log n}\}$: that replacement gives a tighter interval. Thus assume $\omega \to \infty$ and $\omega =o(\log n)$, and putAt $p_{-}$, let $J$ count isolated vertices in $L$. The same indicator random variable calculation as for all isolated vertices givesBy the Chebyshev inequality, $J>0$ with high probability. Since $\ell \ge 2$ eventually, the marked vertices are then not all connected.

At $p_{+}$, the logarithmic-regime giant component result applies with $k=2$ and any fixed ${\gamma }_0\in (1/3,1/2)$. Its unique giant component misses $(1+o(1))n^{1/2}{e}^{-\omega /4}$ vertices. On the event that it misses at most twice that number, exchangeability makes the missed vertex set uniform conditional on its size. A union bound therefore givesThus all of $L$ is connected at $p_{+}$ with high probability.

For the uniform random graph process, assign uniform labels to the edges of the complete graph as independent random variables and reveal them in label order. The binomial random graph $G(n,p)$ is the prefix containing the $M(p)$ labels at most $p$, where $M(p)$ has a binomial distribution with parameters $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $p$. Its variance at $p_{\pm }$ is $O(n\log n)$, whereas the gap between $\mathbb{E}M(p_{\pm })$ and the relevant endpoint $m_{\pm }$ is $(1+o(1))\omega n/8$. The Chebyshev inequality gives $M(p_{-})\ge m_{-}$ and $M(p_{+})\le m_{+}$ with high probability, with harmless integer rounding. The monotone graph property that all marked vertices are connected now impliesThe marked-set connectivity threshold is lower than the threshold for connecting every vertex, because only about $\sqrt{n}$ specified vertices need to avoid the small graph components.

Let $a=kn/(2k+1)$, $u=(k+1)n/(2k+1)$ and $b=u/k$. A graph cut with no crossing edges is obtained by assigning whole graph components to its two sides. Among all such assignments, maximize the smaller side's size $S\le n/2$, and write $T=n-S$ for the other side.

Suppose $S<a$. Then $T>u=kb$. If a graph component on the larger side had size $0<w<n-2S$, moving it to the smaller side would make both $S+w$ and $T-w$ greater than $S$. That contradicts maximality. Hence every graph component on the larger side has at least $n-2S$ vertices. Since each has at most $b$ vertices and their total exceeds $kb$, there must be at least $k+1$ of them. Consequentlya contradiction. Thus $a\le S\le T\le u$, proving the required empty cut with both sides at most $(k+1)n/(2k+1)$. This balanced component cut argument works for arbitrary positive component weights as well; it does not require divisibility of $n$.

If some choice $\omega$ produced a graph with largest component of a graph smaller than $2n/3$, the balanced component cut result with packing parameter one would give an empty graph cut whose sides both have at least $n/3$ vertices. For any fixed such vertex set partition, a uniform edge of the complete graph crosses with probabilityTo avoid crossing in row $i$, at least one of its $k$ offered edges must be noncrossing. The row's probability is $1-q^k\le 1-(4/9{)}^k$. The rows consist of independent random variables, so at $m=cn$ a union bound over at most $2^n$ vertex set partitions givesFor example, the positive integermakes this bound at most $e^{-n}$. Therefore every choice has a component of order at least $2n/3$, with probability tending to one. The simultaneous giant for fixed random-edge choice estimate includes choices made after seeing the entire array; it does not assume a particular online selection rule.

Assume $0<\lambda =1-\epsilon <1$, as required for this nontrivial subcritical binomial random graph. Put $\delta =\lambda -1-\log \lambda >0$. A breadth-first exploration of a binomial random graph is dominated by a Galton-Watson process whose offspring counts are independent random variables with law $\mathrm{Bin}(n,\lambda /n)$. If its total progeny $T$ is at least $j$, the first $j-1$ offspring counts sum to at least $j-1$. Their moment-generating function is bounded by that of a Poisson distribution of mean $\lambda (j-1)$. The exponential Markov inequality, optimized at $t=-\log \lambda$, yieldsTaking $j=\lceil (1+\eta )\log n/\delta \rceil$ for any fixed $\eta >0$, a union bound over all starting vertices gives $\mathbb{P}(L_1\ge j)=o(1)$.

For the matching lower bound, let $X_j$ count tree components of order $j$. The tree-component expectation in the Erdős-Rényi model is exactlyFor $j=O(\log n)$, the Stirling formula givesChoose $j=\lfloor (1-\eta )\log n/\delta \rfloor$, with $0<\eta <1$. Then $\mathbb{E}{X}_j\to \infty$. Distinct overlapping vertex sets cannot both be graph components. For disjoint sets, the joint probability differs from the product only because the $j^2$ between-set edges were counted twice as absent. ThusIt follows that $\mathrm{var}{X}_j/(\mathbb{E}{X}_j{)}^2=o(1)$. The second moment method gives $X_j>0$ with high probability. Combining both bounds, and then taking arbitrarily small fixed $\eta$, proves the sharp subcritical largest-component scaleFinally the Taylor expansion of $-\log (1-\epsilon )$ gives $\delta ={\epsilon }^2/2+{\epsilon }^3/3+\cdots$. The endpoint $\lambda =0$ has no edges and is excluded from this logarithmic asymptotic.

The function $x{e}^{-x}$ is strictly increasing on $(0,1)$ and strictly decreasing on $(1,\infty )$. Hence for each $\lambda >1$ there is a unique $\theta ={\lambda }^{\ast }\in (0,1)$ with $\theta e^{-\theta }=\lambda e^{-\lambda }$.

Apply the subcritical component estimates to $G(n,\theta /n)$. For a specified vertex, the exact tree-component expectation in the Erdős-Rényi model gives the limiting probability that it lies in a tree component of order $j$:For each fixed $j$, the probability of a non-tree graph component of that size is $O_j(1/n)$: a spanning tree and one extra edge are necessary. Moreover the Galton-Watson process exploration estimate from the preceding proof bounds the probability of order greater than $K$ by $e^{-{\delta }_{\theta }(K-1)}$, uniformly in $n$, where ${\delta }_{\theta }=\theta -1-\log \theta >0$. First let $n\to \infty$ for fixed $K$, then let $K\to \infty$. No probability mass escapes to large components or non-tree components, so ${\sum }_{j\ge 1}{a}_j=1$. Multiplying by $\theta$ and using its defining identity givesEquivalently, the rooted-tree generating function selects the smaller solution of $T{e}^{-T}=\lambda e^{-\lambda }$. The choice of that branch is essential; the larger solution $\lambda$ is not the value of this convergent series.

For the binomial branching process, the offspring probability generating function is $f(s)=(1-p+ps{)}^n$. The Galton-Watson extinction fixed point gives $1-\rho =f(1-\rho )=(1-p\rho {)}^n$.

The printed finite-binomial upper bound is false without an additional asymptotic qualification. For $n=2$ and $p=(1+\epsilon )/2$, solving the fixed-point equation exactly givesFor instance $\epsilon =1/20$ gives $\rho =80/441>1/10=2\epsilon$. More generally, at every fixed $n>1$ the Taylor expansion gives $\rho =2n\epsilon /(n-1)+O_n({\epsilon }^2)$, again contradicting that upper bound for sufficiently small positive $\epsilon$.

Here is the corrected binomial branching survival correction. The Poisson branching process of mean $1+\epsilon$ has branching survival probability $r$ satisfying $-\log (1-r)=(1+\epsilon )r$. Expanding the logarithm givesThus $2\epsilon /(1+2\epsilon )\le r\le 2\epsilon$, which implies the requested lower estimate $r\ge 2\epsilon -4{\epsilon }^2$. Since $(1-p+ps{)}^n\le e^{np(s-1)}$ on $[0,1]$, iteration of the two offspring probability generating functions gives $\rho \ge r$.

For the actual binomial branching process, expansion of its exact fixed-point equation givesIf $(1+\epsilon {)}^2<n$, all coefficients are nonnegative. Keeping the first term provesIn particular, for $n\to \infty$ and $\epsilon =o(1)$ this gives $\rho =2\epsilon +O({\epsilon }^2+\epsilon /n)$. The printed bounds also hold for the binomial branching process in an explicit large-$n$ regime: $0<\epsilon \le 1/4$ and $n\epsilon \ge 2$. Indeed these conditions give $n{p}^2\le \epsilon$ and $n{p}^3\le 1/4$. In the preceding nonnegative series, evaluation at $x=2\epsilon$ givesThe series is increasing, and its value at the actual branching survival probability $\rho$ is $\epsilon$, so $\rho \le 2\epsilon$. Together with the lower bound already proved, this recovers $2\epsilon -4{\epsilon }^2\le \rho \le 2\epsilon$ in that regime. In particular it applies eventually to part (ii). The counterexample shows why a regime condition is needed for a literal finite-$n$ statement.

Write $\mu =1+\epsilon$, $p=\mu /n$, $q=1-p$, and let $T$ be the total progeny of a binomial branching process. The preceding binomial branching survival correction gives $\rho =(2+o(1))\epsilon$. For a branching process conditioned on extinction, the offspring probability generating function is $f((1-\rho )s)/(1-\rho )$, with meanfor sufficiently large $n$. Summing expected generation sizes therefore gives $\mathbb{E}[T;T<\infty ]=(1-\rho )/(1-f^{\prime }(1-\rho ))=O(1/\epsilon )$.

Put $K=\lceil {\epsilon }^{-3}\rceil$ and let $N_{\ge K}$ count vertices in graph components of order at least $K$. A breadth-first exploration of a binomial random graph is dominated by $T$. The Markov inequality applied to finite total progeny givesAlways $L_1\le K+N_{\ge K}$. Since $n{\epsilon }^4\ge n^{1/3}\to \infty$, we have $K=o(\epsilon n)$ and $n/(\epsilon K)=O(n{\epsilon }^2)=o(\epsilon n)$. Hence $\mathbb{E}{L}_1\le (2+o(1))\epsilon n$. This bound controls the expected value directly, including rare large graph components.

For the lower bound, use the breadth-first exploration of a binomial random graph with $U_t$ unseen vertices, $A_t$ active vertices and $t$ explored vertices, starting from $U_0=n$, $A_0=0$. Let $b_t=1_{\{A_{t-1}=0\}}$ indicate a new root. Conditional on the past, the newly discovered count $Z_t$ has a binomial distribution $\mathrm{Bin}(U_{t-1}-b_t,p)$. Put $D_t=Z_t-p(U_{t-1}-b_t)$. The unseen-count recursion givesHere $M_t$ is a martingale. Up to $T_0=\lceil 3\epsilon n\rceil$, martingale-difference orthogonality gives $\mathbb{E}{M}_{T_0}^2\le C\epsilon n$, since each conditional variance is at most $np<2$ and $q^{-2T_0}$ is bounded.

Take $h=\sqrt{\epsilon }+(n{\epsilon }^3{)}^{-1/8}$. Then $h\to 0$, $\epsilon =o(h)$ and $h^{2}n{\epsilon }^3\to \infty$. The Doob L2 maximal inequality impliesThe Taylor expansion, uniformly for $t\le T_0$, gives $F(t)=\epsilon t-t^2/(2n)+O({\epsilon }^{3}n+\epsilon )$. Thus $F(t)\ge h{\epsilon }^{2}n/3$ throughout the integer interval $[\lceil h\epsilon n\rceil ,\lfloor (2-h)\epsilon n\rfloor ]$ for large $n$. The new-root sum is nonnegative, so on the preceding event $A_t>0$ throughout this interval. No graph component finishes there: all these explored vertices belong to one graph component, of order at least $(2-2h)\epsilon n-O(1)$, with high probability. Its expected value is therefore at least $(2-o(1))\epsilon n$. Combining both inequalities provesThe barely-supercritical largest-component expectation uses both a positive exploration window and a finite-progeny bound; a bare convergence-in-probability assertion would not by itself justify this expectation.

Use the standard Achlioptas process with two independent uniform candidate edges per step and a rule choosing one. The component-band vertex count $N_{[k,Dk)}$ counts vertices, not the number of graph components. Integer time rounding changes the arguments below by $O(1)$ steps.

First, at $t_k$ the eventual graph component of order at least $\delta n$ is assembled from graph components already present at $t_k$. Contract those initial graph components. During $s=t_c-t_k$ steps, at most $s$ new edges are added, so the eventual connected contracted graph contains at most $s+1$ initial graph components. Initial graph components of order less than $k$ can therefore contribute at mostvertices, for sufficiently large $n$ and fixed $k$, since $s=\delta n/(2k)+O(1)$. For $k=1$ their contribution is zero. Consequently $N_{\ge k}(G_{t_k})\ge \delta n/2$.

We now use forced merging of large components. If at a time $m$ the graph components of order at least $K$ contain at least $an$ vertices, then after at most $A(a)n/K+O(1)$ steps there is a graph component of order at least $an/3$, except on an event of probability exponentially small in $n/K$. One explicit choice is $A(a)=81(\log 2+2)/a^4$. The proof is a union bound over set partitions of the at most $n/K$ initial large graph components: if all final graph components were small, a balanced component cut would split their initial vertices into sets of size at least $an/3$, and both candidate edges cross that fixed cut with probability at least $a^4/81$ in every step. The rule cannot avoid such a forced crossing. The failure bound is $e^{-2n/K}$, and a union bound makes the estimate simultaneous over all starting times at most $3n$, for each fixed $K$.

Set $a=\delta /4$ and choose a fixed integer $D\ge 2$ with $D\ge 4A(a)/\delta$. If $N_{\ge Dk}(G_{t_k})\ge \delta n/4$, this lemma would produce a graph component of order at least $\delta n/12$ by timeThat contradicts the assumed $L_1(G_{t_c^{\prime }})=o(n)$. Thus $N_{\ge Dk}(G_{t_k})<\delta n/4$, and subtraction givesThe same $D$ works for every fixed $k$; it depends only on $\delta$, with the number of offered edges fixed at two.

The persistence of unsampled graph components prevents the mass from each size band from disappearing entirely before $t_c$. More precisely, a band $[k,Dk)$ containing at least $\delta n/4$ vertices retains at least $\beta n$ vertices in that same band after at most $n/k$ steps, with high probability, for a fixed $\beta >0$ depending only on $\delta ,D$. To see why, each initial graph component in that band has a fixed positive probability that none of the offered edge endpoints touches it during the interval. Such a graph component remains unchanged regardless of the selection rule. The McDiarmid inequality concentrates the total mass of these untouched graph components. The reusable lemma supplies the full uniform-in-starting-time argument, including the version that samples absent edges.

Choose finitely many disjoint bands $[D^j,D^{j+1})$, $j=0,\dots ,J$, with $(J+1)\beta >1$. Part (i) provides at least $\delta n/4$ vertices in band $j$ at its time $t_{D^j}$. Each interval from that time to $t_c$ has length at most $n/D^j$, so persistence leaves at least $\beta n$ vertices in every one of these disjoint bands at the common time $t_c$. A union bound over this fixed finite number of bands makes all the conclusions simultaneous. Their total exceeds $n$, a contradiction. No fixed two-choice Achlioptas rule satisfies the explosive percolation hypothesis.

This continuity of fixed-choice percolation is the fixed-choice obstruction proved by Riordan and Warnke; their original research paper also treats a broader class of rules. The argument here does not apply when the number of offered choices grows with $n$.