Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 12 (Random Graphs)

It suffices to find a tree component of order $k$. Let $X$ count such graph components in the binomial random graph. The Cayley formula and independent edges give the tree-component expectation in the Erdős-Rényi modelHere $k$ is fixed. The upper bound on $p$ implies $p=O(\log n/n)$, hence $n{p}^2=o(1)$ andWe first verify that this expected value diverges throughout the permitted interval, including when $\omega$ grows quickly. If $np\le 1$, the exponential factor is at least $e^{-k}$ and $n^k{p}^{k-1}\ge {\omega }^{k-1}$. If $1\le np\le (\log n)/(2k)$, then $n(np{)}^{k-1}{e}^{-knp}\ge \sqrt{n}$. Finally, if $np\ge (\log n)/(2k)$, the upper bound on $p$ givesThus $\mu \to \infty$ in all three cases.

For distinct $k$-element vertex sets $S,T$, write $I_S,I_T$ for their tree-component indicators. If they overlap, they cannot both be distinct connected components of a graph, so $\mathbb{E}(I_S{I}_T)=0$. If they are disjoint, the absent edges between the two sets are counted twice in the product of their marginal probabilities and once in the joint probability. ThereforeSumming and discarding the negative overlap contributions yieldsThe Chebyshev inequality now gives $\mathrm{Pr}(X=0)\le \mathrm{Var}X/{\mu }^2\to 0$. Consequently there is a component of order $k$ with high probability, in fact a tree component. The argument proves the entire fixed-order tree-component window, rather than only a particular choice of $p$.

Let $X_t$ count $t$-cliques, and put ${\mu }_t=\left(\genfrac{}{}{0ex}{}{n}{t}\right)p^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$. Since ${\mu }_{r+1}\to 0$, the Markov inequality gives $\mathrm{Pr}(X_{r+1}>0)\to 0$. Any larger clique contains an $(r+1)$-clique, so it remains to prove $X_r>0$ with high probability.

We give the required growing-clique overlap bound explicitly. Set $\mu ={\mu }_r$ and, for $2\le s\le r$,The quantity $a_s$ is the probability that a uniformly chosen $r$-set overlaps a fixed $r$-set in exactly $s$ vertices. Two clique indicators share exactly $\left(\genfrac{}{}{0ex}{}{s}{2}\right)$ edge requirements, so their joint-to-product ratio is $p^{-\left(\genfrac{}{}{0ex}{}{s}{2}\right)}$. Overlap zero or one gives independence. Hence the overlap formula for the variance of a clique count impliesWe must bound this sum with $r$ allowed to grow.

Eventually ${\mu }_r\ge 1$ and ${\mu }_{r+1}\le 1$. Using $(n/t{)}^t\le (\genfrac{}{}{0ex}{}{n}{t})\le (en/t{)}^t$, these inequalities giveFor $2\le s\le r/2$, a union bound over the $s$ selected shared vertices gives $a_s\le \left(\genfrac{}{}{0ex}{}{r}{s}\right)(r/(n-r){)}^s$. Put $a=(s-1)/(r-1)<1/2$. Since $n\ge r^3$ and $n-r\ge n/2$,For each fixed $s$, the first bound tends to zero if $r$ stays bounded, because its power of $n$ is negative. If $r\to \infty$, the middle bound tends to zero because $a\to 0$. Thus each fixed-$s$ term tends to zero along arbitrary admissible sequences. The bounding series ${\sum }_{s\ge 2}(2e^2/s{)}^s$ converges. Splitting at a fixed large index, then taking $n\to \infty$ and the index to infinity, proves that the entire lower-half sum is $o(1)$.

For the upper half write $s=r-j$. The exact diagonal comparison isFor $1\le j\le r/2$, the second bound on $p$ givesThe last inequality uses $n\ge r^3$: the exponent of $n$ in the bracket is negative, so substituting $n=r^3$ bounds it above. Uniformly for this range of $j$, $r^{2(j+1)/r}\le 9j$. Indeed $r^{2/r}\le 3$, and concavity of $\log (3j)-(2j/r)\log r$, checked at $j=1$ and $j=r/2$, gives $r^{2j/r}\le 3j$. It follows thatThus $\mathrm{Var}{X}_r=o({\mu }^2)$. The second moment method gives $\mathrm{Pr}(X_r=0)\to 0$. Combining this with the absence of larger cliques provesThe restriction on $r$ is used in both overlap ranges; divergence of a clique count in a binomial random graph alone would not suffice for arbitrary growing $r$.

Couple the uniform random graph process by giving every possible edge an independent uniform label in $[0,1]$ and revealing them in increasing order. The graph at label threshold $p$ is a binomial random graph. Define ${\tau }_0$ as the first step with no isolated vertices and ${\tau }_c$ as the first connected graph. Deterministically ${\tau }_c\ge {\tau }_0$. We prove the reverse inequality with high probability by tracking the same process through a short interval.

Put $w=\frac{1}{4}\log \log n$, $p_{\pm }=(\log n\pm w)/n$, and $L=n{p}_{-}$. At $p_{-}$ the isolated vertex count $Z$ hasThe variance estimate follows by comparing two isolated-vertex indicators, whose joint-to-product probability ratio is $(1-p_{-}{)}^{-1}$. Thus $Z>0$ with high probability. Also the Markov inequality gives $Z\le \log n$ with probability tending to one.

At this same threshold, exclude every graph component with order $2\le s\le n/2$. For $2\le s\le n/\log n$, any such component contains a spanning tree. The Cayley formula and a union bound therefore giveIn this range the bracket is at most $A=e^{2}L{e}^w/n=o(1)$. Summing over $s\ge 2$ gives $O(n{A}^2/L)=O(L{e}^{2w}/n)=o(1)$. For $n/\log n<s\le n/2$, even the cut-absence bound is enough:The bracket tends to zero, so this range also has total probability $o(1)$. Consequently the graph at $p_{-}$ consists of one component of order greater than $n/2$ and its isolated-vertex set $S$, where $1\le |S|\le \log n$ with high probability.

Conditional on the entire graph at $p_{-}$, every unrevealed edge label remains independently uniform on $(p_{-},1)$. In particular,There are no isolated vertices at $p_{+}$ with high probability, because their expected value is asymptotic to $e^{-w}\to 0$. On the intersection of these events, each vertex of $S$ loses isolation by joining the original large component, never by forming a separate small component with another vertex of $S$. At every step between these two thresholds there is therefore one nontrivial component and some isolated vertices. The final isolated vertex disappears precisely when the graph becomes connected. This proves the connectivity hitting time equals disappearance of isolated vertices result:

For the critical-window probability, let $p=(\log n+\alpha (n))/n$ with $|\alpha (n)|\le B$. For each fixed $j$, the falling factorial moment of the isolated-vertex count isuniformly for such shifts. Apply the Bonferroni inequalities to the zero-count event. Its odd and even truncations bracket $\mathrm{Pr}(Z=0)$ by partial sums of ${\sum }_{j\ge 0}(-1{)}^j{e}^{-j\alpha (n)}/j!$. Since $e^{-\alpha (n)}\le e^B$, their remainders tend uniformly to zero. Hence $\mathrm{Pr}(Z=0)=e^{-e^{-\alpha (n)}}+o(1)$. The process equality just proved changes this probability by at most its $o(1)$ failure probability. ThereforeThe ratio follows because the denominator is bounded below by $e^{-e^B}>0$; no convergence of $\alpha (n)$ is needed.

The printed second conclusion has the complementary denominator and is false as written. For $\alpha (n)=0$, the printed ratio tends to $e^{-1}/(1-e^{-1})=1/(e-1)\ne 1$. Its denominator $1-e^{-e^{-\alpha (n)}}$ is correct for the probability of being disconnected. Thus either remove the leading $1-$ in the denominator or replace “connected” by “disconnected”; the proof supplies both corrected versions.

Put $M=2m$ and $a_i=\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)$. Use the configuration model: give vertex $i$ exactly $d_i$ labelled half-edges and choose a uniform perfect matching of all $M$ half-edges. There arepairings, with $(2m{)}_m$ denoting a falling factorial. Each allowed simple graph has exactly ${\prod }_i{d}_i!$ representations: at every vertex, assign its incident graph edges bijectively to its labelled half-edges. Therefore its enumeration reduces to the probability that a pairing is simple and avoids $G_0$.

Count three kinds of prescribed bad patterns. A loop pattern consists of a pair of half-edges at one vertex. A double-edge pattern consists of two half-edges at each of two distinct vertices and one of their two cross-pairings. A forbidden-edge pattern consists of one half-edge at each endpoint of an edge of $G_0$. Let their respective counts in the random pairing be $Z_L,Z_D,Z_F$. Simplicity and avoidance are equivalent to $Z=Z_L+Z_D+Z_F=0$, including exclusion of triple edges because those contain double-edge patterns.

A prescribed collection of $t$ disjoint half-edge pairs occurs with probabilityConsequently the bad-pattern expected values areHere $\lambda =({\sum }_i{a}_i)/m$ and $\mu =M^{-1}{\sum }_{ij\in E(G_0)}{d}_i{d}_j$, as in the PDF. Since $1\le d_i\le \Delta$ and $G_0$ has bounded maximum degree, $M=\Theta (n)$ and all three means are uniformly bounded. For the double-edge estimate, ${\sum }_i{a}_i^2=O(n)$, so its contribution after division by $M^2$ is $o(1)$.

We now give the moment-counting step rather than assume independence. For each fixed $h$, expand the factorial moment $\mathbb{E}(Z{)}_h$ as the sum over ordered distinct bad patterns. Collections on disjoint vertex sets have, by the displayed pairing probability, joint probabilities equal to the product probabilities times $1+O(1/n)$. Their total contribution isDeleting collections with a shared vertex changes the independent-product sum by $O(1/n)$, since all ordinary and forbidden vertex degrees are bounded.

For actual joint probabilities of overlapping patterns, incompatible uses of a half-edge give zero. Compatible collections with no shared paired edge lose at least one free vertex choice, without reducing the number of required pairs, so contribute $O(1/n)$. A shared paired edge can occur only between two double-edge patterns or between a double-edge pattern and a forbidden-edge pattern. In the first case their union requires at least three parallel paired edges: there are $O(n^2)$ endpoint choices and probability $O(n^{-3})$. In the second case the endpoint pair must be an edge of $G_0$: there are only $O(n)$ choices and at least two required pairs, giving $O(n^{-1})$. Adding further patterns in a fixed collection does not remove this deficit: a disjoint addition contributes bounded order, while an addition to an existing cluster has only bounded half-edge choices unless it supplies new free vertices, compensated by its new required pairs. Summing the finitely many overlap types for fixed $h$ therefore gives $o(1)$. Thus, with $\Lambda =\lambda /2+{\lambda }^2/4+\mu$,The Bonferroni inequalities bracket $\mathrm{Pr}(Z=0)$ by the odd and even partial sums of ${\sum }_h(-1{)}^h\mathbb{E}(Z{)}_h/h!$. The means $\Lambda$ are bounded, so the corresponding exponential-series remainders vanish uniformly as the truncation increases. Taking $n\to \infty$ and then the truncation to infinity proves the bounded-degree pairing avoidance estimate $\mathrm{Pr}(Z=0)=e^{-\Lambda }+o(1)$. This does not require $\lambda$ or $\mu$ to converge. The exponential is bounded away from zero, so the additive error is also a relative $o(1)$ error.

Multiplying by the pairing count and dividing by the representation factor givesThe factor $(2m{)}_m$ multiplies the exponential; it is not part of its exponent. The TeX aid misgroups this factor, whereas the original PDF is unambiguous. The bounded-degree proof also covers the stated additional assumption $2m-n\to \infty$.

Begin with the configuration model for $n$ labelled vertices of degree $r$. Let $Y_{\ell }$ count cycles in a graph with specified paired edges, so parallel-edge choices are counted separately before conditioning. Choose a cyclic ordering of $\ell$ distinct vertices in $(n{)}_{\ell }/(2\ell )$ ways, where division by $2\ell$ removes rotation and reversal. At each vertex choose an ordered pair of distinct half-edges for the entering and leaving edges, in $r(r-1)$ ways. These $\ell$ prescribed pairs appear with the pairing probability from part (i), givingIt remains to justify conditioning on simplicity: merely dividing by a positive simplicity probability would give an incorrect constant.

Unconditionally, part (i) with no forbidden graph has $\lambda =r-1$, soCondition on one specified cycle pairing. The unpaired half-edges form a uniform configuration model with degree $r-2$ at its $\ell$ vertices and degree $r$ elsewhere. A completion of the full graph is simple exactly when the residual graph is simple and has no additional edge along one of the already prescribed cycle edges. This forbidden graph has maximum degree two. Because $r,\ell$ are fixed,After permuting labels if needed to sort the degrees, the assumptions of part (i) still hold, including residual degrees at least one. Its bounded-degree pairing avoidance estimate therefore shows thatThis ratio is the same for each prescribed cycle, by symmetry. Sum over their indicators to obtain $\mathbb{E}(Y_{\ell }\mid \text{simple})=(1+o(1))\mathbb{E}{Y}_{\ell }$. Conditioning is uniform over all simple $r$-regular graphs because each has $(r!{)}^n$ pairing representations. On simplicity, $Y_{\ell }$ is the ordinary cycle count. Hence the short-cycle expectation in a uniform regular graph is

We first establish the labelled forest count with prescribed roots. For a prescribed root set $R$ of size $k<n$, orient each tree toward its unique root. Repeatedly delete the smallest remaining nonroot leaf, recording its parent. There are $n-k$ deletions, and the final recorded parent belongs to $R$. Conversely, start with any code of length $n-k$ whose last entry lies in $R$. At each step select the smallest remaining nonroot absent from the remaining code, connect it to the code's first entry, and delete that vertex and entry. Such a vertex exists: among $s$ remaining nonroots, the remaining code has $s$ entries but at least its last entry is a root, so at most $s-1$ nonroots occur in it. Previously deleted vertices never recur in the code, so the selected parent is still present. Every edge goes from a vertex being deleted to one retained, excluding a cycle. The resulting forest has one root in each graph component, and the two constructions are inverse. Its count is thereforefor $k=n$, interpret this as one, the empty forest.

A connected simple graph with $n$ edges has exactly one cycle: a spanning tree uses $n-1$ edges, and the remaining edge creates its unique cycle. If that graph cycle has length $k$, choose its vertex set in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways and its unoriented cyclic order in $(k-1)!/2$ ways. All other edges form a forest rooted at those $k$ vertices, with exactly one cycle vertex per forest component; two roots in one attached component would create an additional cycle. Conversely every such cycle and rooted forest gives a unique unicyclic component. ThusThis is the labelled unicyclic graph count. The term $k=n$ correctly counts a cycle with no attached nonroot vertices.

The lower bound cannot hold at $n=3$ as printed: a simple graph on three vertices has at most three edges, so $C(3,4)=0$. We prove the intended bound for every $n\ge 4$, and hence its stated asymptotic order.

Delete leaves from a connected graph of graph excess one to obtain its nonempty 2-core. Deleting a leaf and its incident edge preserves edges minus vertices. The deleted part is a forest rooted at the core vertices: it cannot contain a cycle, which would survive deletion, and it cannot join two core vertices, since the joining path would itself survive. The 2-core remains connected. Suppress its maximal paths with degree-two internal vertices, allowing coincident endpoints for a cycle based at a branching vertex. The resulting graph kernel is a connected multigraph of minimum degree at least three, retaining loops and parallel edges, with the same excess one.

In that kernel,Thus it has either one degree-four vertex or two degree-three vertices. In the first case its two edges are loops. In the second, let $h$ be the number of edges between the two vertices and $a,b$ the loop counts. Connectivity gives $h\ge 1$, and $2a+h=2b+h=3$, leaving $h=3,a=b=0$ or $h=1,a=b=1$. This proves the bicyclic kernel classification: the two-loop bouquet graph, the three-edge Theta graph, and the two-loop dumbbell graph. Original simple cores are graph subdivisions of these kernels; loops must subdivide to cycles of length at least three, and at most one of the three theta paths can be an unsubdivided edge.

Let $b_k$ count labelled bicyclic cores on a fixed $k$-vertex set. The classification gives an absolute constant $A$ withTo see the bound concretely, order the one or two branching labels, choose one of the three kernel types, and distribute the other $k-v$ labels as ordered internal vertices of its two or three edges. There are at most $\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)=O(k^2)$ weak compositions of their lengths, and at most $k!$ ordered assignments of all labels. This overcounts orientations and edge permutations and ignores simplicity restrictions, both harmless for an upper bound.

For a lower bound, use only theta cores whose three paths each have at least one internal vertex. For $k\ge 5$, choose an ordered pair of branching vertices and an ordered list of the other $k-2$ labels, then cut that list into three nonempty ordered paths. There are $k!\left(\genfrac{}{}{0ex}{}{k-3}{2}\right)$ encodings. Every resulting simple theta core is encoded exactly $2\cdot 3!=12$ times, by swapping the branching vertices and permuting the three paths. Hence

Choose the core's vertices and attach the forest counted in part (i). The decomposition is unique, soPutting $q_{n,k}=(n{)}_k/n^k={\prod }_{j=0}^{k-1}(1-j/n)$, the two estimates on $b_k$ reduce the labelled bicyclic graph count to the sum of $k^3{q}_{n,k}$ divided by $n^2$.

For the upper bound, $\log (1-x)\le -x$ givesThe corresponding sum is $O(n^2)$. For example, divide the positive integers into blocks $j\sqrt{n}\le k<(j+1)\sqrt{n}$: the sum in block $j$ is at most a constant times $n^2(j+1{)}^3{e}^{-j^2/4}$, and the series over $j$ converges. Including the finitely small indices makes no difference. Therefore $C(n,n+1)\le c_2{n}^{n+1}$.

For the lower bound, take $n$ sufficiently large and $\sqrt{n}\le k\le 2\sqrt{n}$. Then $k\ge 8$, and $j/n\le 1/2$ throughout the product. Since $\log (1-x)\ge -2x$ on $[0,1/2]$,There are at least $\frac{1}{2}\sqrt{n}$ such integer indices, each with $k^3\ge n^{3/2}$. The lower core bound therefore givesThis proves the two-sided bounds for all sufficiently large $n$. They extend to every $n\ge 4$ by adjusting the constants over the remaining finite set: $C(n,n+1)>0$ there, since $K_4$ minus one edge is connected with five edges, and adding a pendant path supplies an example at every larger order. Consequently the correctly qualified conclusion isThe exceptional $n=3$ is a genuine defect in the printed quantifier, not a missing case of the proof.