Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 12 (Probabilistic Combinatorics)

Write $N={\sum }_{i=1}^n{1}_{E_i}$, and put $S_0=1$, $S_j={\sum }_{|I|=j}\mathrm{Pr}({\bigcap }_{i\in I}{E}_i)$ for $j\ge 1$. Counting the $j$-subsets of the events that occur gives $S_j=\mathbb{E}\left(\genfrac{}{}{0ex}{}{N}{j}\right)$. Set $S_j=0$ for $j>n$. The Jordan-Bonferroni exact-occurrence inequalities areHere $k\ge 0$ is an integer. To prove both bounds, evaluate the truncated expression before taking its expectation. At an integer value $N=j\ge k$ it equalsFor $j=k$ this is one. For $j>k$, Pascal's identity, or an induction on $m$, givesFor $j<k$ the original expression is zero. Thus its difference from $1_{\{N=k\}}$ is everywhere nonnegative for even $m$ and nonpositive for odd $m$. Taking expectations proves the inequalities, including $k=0$.

For a general nonnegative integer-valued random variable, define its factorial moment by ${\mathbb{E}}_r(X)=\mathbb{E}(X{)}_r$, where $(X{)}_r$ is the falling factorial and ${\mathbb{E}}_0(X)=1$. The same pointwise calculation applies to $X$, so putEvery required moment is finite under the given limit assumption: eventual finiteness of higher factorial moments implies finiteness of the lower ones. The neighbouring upper and lower bounds differ in absolute value byThe last ratio tends to one, and the first factor involving the moment tends to zero. Since $\mathrm{Pr}(X=k)$ lies between every two such neighbouring bounds, each $T_m$ tends to it. Consequently the factorial-moment inversion isThis proves convergence of the signed series without an unjustified interchange with an expectation.

For any prescribed $r\ge 1$, take $\mathrm{Pr}(X=j)=C_r{j}^{-(r+2)}$ for $j=1,2,\dots$, with $C_r=[{\sum }_{j\ge 1}{j}^{-(r+2)}{]}^{-1}$. Since $(j{)}_r\sim j^r$ and $(j{)}_{r+1}\sim j^{r+1}$, the two moment sums have tails comparable respectively to $\sum j^{-2}$ and $\sum j^{-1}$. Thus ${\mathbb{E}}_r(X)<\infty$ but ${\mathbb{E}}_{r+1}(X)=\infty$, as required.

Take $c>0$ and $e>0$, as required for the displayed sparse scaling and the later normalization. A strictly balanced graph satisfies $e(F)/v(F)<e/v$ for every proper nonempty subgraph $F\subset H$. This forces $H$ to be connected and to have no isolated vertices: otherwise a component of at least the average density, or deletion of the isolated vertices, violates strict balance. Copies here are subgraphs, not induced subgraphs.

For fixed $r$, the factorial moment ${\mathbb{E}}_r(X_H)$ counts ordered $r$-tuples of distinct copies all present in the binomial random graph. The contribution of vertex-disjoint copies is exactlyThe factor $a^{-r}$ removes the multiple embeddings of each copy coming from its graph automorphisms. For an overlapping tuple, let $U$ be its union. There are $O(n^{v(U)})$ placements of each fixed union type, and the probability its edges are present is $p^{e(U)}$. When adding a copy meeting the earlier union in $f$ vertices and $g$ edges, the exponent $v(U)-(v/e)e(U)$ changes byIt is strictly negative if this intersection is a proper nonempty subgraph, and zero only for an empty intersection or a whole copy. In particular the first vertex-overlapping copy has a proper nonempty intersection: the preceding copies are vertex-disjoint, and a connected copy contained in their union would have to equal one of them, contrary to distinctness. Its contribution is therefore strictly negative; later additions cannot undo that loss. Only finitely many union types occur for fixed $r$, so their total contribution is $o(1)$. We have proved all the factorial moment limits, and the allowed factorial-moment criterion for Poisson convergence givesThis is the Poisson limit for strictly balanced subgraph counts.

The pendant-edge graph has density $7/5$, whereas its proper $K_4$ core has density $6/4$. Thus $K_4^{+}$ is not strictly balanced. The complete graph $K_4$ is strictly balanced, with 24 graph automorphisms, so at $p=c{n}^{-2/3}$ its copy count $Z$ tends to $\mathrm{Po}(c^6/24)$.

Every $K_4^{+}$ copy has a unique four-vertex clique core and one selected edge joining it to a fifth vertex. For any four-set $C$, let $D_C$ count the ambient edges between $C$ and its complement. Then $D_C\sim \mathrm{Bin}(4(n-4),p)$, with mean ${\mu }_n\sim 4c{n}^{1/3}$. It is independent of the internal edges determining whether $C$ is a clique. Choose ${\delta }_n=n^{-1/12}$. A Chernoff bound and a union bound giveTherefore, simultaneously for every actual core, its number of pendant extensions is $(1+o(1))4c{n}^{1/3}$. Extra ambient edges cause no overcount: each selected seven-edge subgraph has exactly one core and one pendant edge. Summing over the cores yieldsbecause $Z$ is uniformly tight. This is the pendant extensions of sparse clique copies mechanism. For $0<\epsilon <1$, neither endpoint of $(k-\epsilon ,k+\epsilon )$ is an integer, and its only nonnegative integer is $k$. Convergence in distribution consequently givesThe positive-$c$ assumption matters: the quotient printed in the question is undefined when $c=0$.

If the random k-out graph with $k=2$ is disconnected, one of its connected components of a graph has size $3\le s\le n/2$. The lower bound follows because every vertex chooses two distinct neighbours inside its component. For a specified $s$-set $S$, absence of crossing edges requires every choice at a vertex in $S$ to stay in $S$, and every choice outside to stay outside. Independence of choices at different vertices gives exactlyFor $3\le s\le n/2$, the two ratios are at most $(s/n{)}^2$ and $(1-s/n{)}^2$. Indeed each of the factors $(s-j)/(n-j)$, $j=1,2$, is at most $s/n$, and the complementary statement is identical. Put $t=s/n$. The binomial coefficient bound $\left(\genfrac{}{}{0ex}{}{n}{s}\right)\le t^{-s}(1-t{)}^{-(n-s)}$ follows by bounding the probability of $s$ successes in $\mathrm{Bin}(n,t)$ by one. Thus the union bound givesFor $s\le \sqrt{n}$, the last summands are at most $n^{-s/2}$, whose sum from three tends to zero. For $s>\sqrt{n}$, they are at most $2^{-s}$, again summing to zero. ThereforeThe proof bounds all possible small components rather than assuming the dependent undirected edges behave like a binomial random graph.

At each vertex independently, take a uniformly random permutation of the other $n-1$ vertices. Use its first two entries for the two-out choices and its first $k$ entries for the $k$-out choices. Every unordered choice set has the prescribed uniform distribution, and choices at different vertices remain independent. This couples the random k-out graphs so that $G_{2\text{-out}}\subseteq G_{k\text{-out}}$ on the same vertex set. Adding edges cannot destroy graph connectivity. ConsequentlyThis establishes connectivity of random k-out graphs for every fixed allowed $k$.

Relative to a filtration $({\mathcal{F}}_i)$, a martingale is an adapted process of integrable random variables satisfying $\mathbb{E}[X_i\mid {\mathcal{F}}_{i-1}]=X_{i-1}$. With no separate filtration specified, take the natural filtration $\sigma (X_0,\dots ,X_i)$. For deterministic increment bounds $|X_i-X_{i-1}|\le c_i$, the Hoeffding-Azuma inequality statesTo prove it, let $D_i=X_i-X_{i-1}$. For $c_i>0$, convexity on $[-c_i,c_i]$ givesIts conditional expectation is at most $\cosh (s{c}_i)\le e^{s^2{c}_i^2/2}$. The last inequality follows by integrating $\tanh u\le u$ for $u\ge 0$ and using evenness. If $c_i=0$ the bound is immediate. Conditional iteration now yields $\mathbb{E}{e}^{s(X_n-X_0)}\le \exp (s^2\sum c_i^2/2)$. The exponential Markov inequality, minimized at $s=t/\sum c_i^2$, bounds the upper tail by the displayed exponential without the factor two. Apply it to $-X_i$ and use the union bound for the two-sided assertion. When every $c_i=0$, the deviation probability is zero.

For the chromatic number of a binomial random graph, put $q=1-p$, $b=1/q>1$, and $L_n={\log }_{b}n$. We prove matching bounds; treating $0<\epsilon <1$ suffices. A colour class is an independent set, so $\chi \ge n/\alpha (G)$. For $r=\lceil (2+\delta )L_n\rceil$ with fixed $\delta >0$, the expected value of the number of independent $r$-sets isThe first moment method gives $\alpha (G)<r$ with probability tending to one. Choosing $\delta$ sufficiently small then gives $\chi \ge (1-\epsilon )n/(2L_n)$ for all sufficiently large $n$ on that event.

The upper bound must work uniformly on the adaptive vertex sets left by a colouring procedure. SetFor a specified $m$-set $U$, its complement graph has distribution $G(m,q)$. Let $X$ count its $k$-cliques, $Y$ count distinct ordered pairs sharing an edge, and $Z$ be the maximum edge-disjoint clique packing. The allowed clique-count estimates at this value of $k$ giveThe overlap quantity, if the diagonal is included, has the exact expression ${\sum }_{j=2}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)\left(\genfrac{}{}{0ex}{}{m-k}{k-j}\right)q^{-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}/\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ after division by $(\mathbb{E}X{)}^2$; the same bound holds. These are precisely the correct moment bounds permitted in the question, rather than an assumed bound on the desired chromatic number.

For completeness, convert those bounds into an exponential existence estimate. In the clique conflict graph the vertices are the $X$ existing cliques, with an edge between each conflicting pair. A random ordering keeps every vertex that precedes all its neighbours. No two retained vertices are adjacent. Their mean number is ${\sum }_{v}1/(d_v+1)\ge X^2/(X+Y)$ by the Cauchy-Schwarz inequality. Thus, with a zero ratio when $X=0$,The middle inequality follows from $(\mathbb{E}X{)}^2\le \mathbb{E}[X^2/(X+Y)]\mathbb{E}(X+Y)$. Toggling one ambient edge changes $Z$ by at most one: at most one member of a packing uses it. Reveal the $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edges successively and form the edge-exposure martingale for $Z$. Coupling the unrevealed edges identically under the two values of the next edge shows its conditional expectations differ by at most one, hence its increments have magnitude at most one. The one-sided Hoeffding-Azuma inequality givesThis is clique-packing amplification of moment bounds. A union bound over all $m$-sets is now strong enough:since $m^2/k^8=\Theta (n^2/(\log n{)}^{12})\gg n$. Thus every such set contains an independent set of size $k$. Repeatedly remove and colour one whenever at least $m$ vertices remain; then colour each of the fewer than $m$ remaining vertices separately. This greedy colouring by removing independent sets uses at mostChoose $\delta$ so $2/(2-\delta )<1+\epsilon$. Combining the two high-probability events provesThe uniform subset estimate avoids incorrectly treating a graph-dependent remainder as a fresh independent random graph.

Let $Z_t$ denote the generation-$t$ type-count vector, and let $p_i^{(t)}={\mathrm{Pr}}_i(|Z_t|>0)$ from a single type-$i$ ancestor. Every type-$j$ child independently has probability $p_j^{(t)}$ of having descendants in generation $t$. For a Poisson random variable $N$ with mean $\lambda$, $\mathbb{E}{s}^N=\exp [\lambda (s-1)]$. Independence across child types therefore givesThe events of nonempty successive generations decrease. Each individual has finitely many children almost surely, so the total tree is infinite precisely when no generation is empty. Consequently $p^{(t)}\downarrow p$, the actual survival probability of a branching process. Continuity of $T$ yieldsThe map $T$ is coordinatewise increasing on nonnegative vectors. Every nonnegative fixed point $p^{\prime }$ automatically lies in $[0,1{]}^l$, since its coordinates equal $1-e^{-z}$ with finite $z\ge 0$. Hence $p^{\prime }\le 1$ and, by induction, $p^{\prime }=T^t(p^{\prime })\le T^t(1)=p^{(t)}$. Taking limits proves $p^{\prime }\le p$ in every coordinate, so $p$ is the greatest nonnegative solution, not merely some fixed point. This argument applies without irreducibility assumptions to the multitype Poisson branching process.

Use row vectors for population counts. Given $Z_t$, independent reproduction has conditional mean $\mathbb{E}[Z_{t+1}\mid Z_t]=Z_t\Lambda$. Starting from $Z_0=e_i^T$, induction gives $\mathbb{E}{Z}_t=e_i^T{\Lambda }^t$. Summing all child types, the expected size of generation $t$ isThis also covers $t=0$, using ${\Lambda }^0=I$. All these finite-generation expectations are finite because the matrix is finite with finite entries.

The necessary and sufficient condition iswhere $\rho$ is the spectral radius of the nonnegative matrix. No irreducibility is required. We use the given nonnegative-vector characterization of its Perron eigenvalue.

For necessity, suppose $p\ne 0$ is the survival fixed point and let $S=\{i:p_i>0\}$. Since $1-e^{-z}<z$ for every $z>0$, its equation gives $(\Lambda p{)}_i>p_i$ for every $i\in S$. There are finitely many such coordinates, soOutside $S$ the inequality $\Lambda p\ge \alpha p$ still holds, because its right side is zero and its left side is nonnegative. The provided Perron–Frobenius theorem characterization therefore gives $\rho (\Lambda )\ge \alpha >1$. In particular survival is impossible at $\rho =1$ for this Poisson offspring law.

Conversely suppose $\rho >1$. The given characterization supplies a nonzero $v\ge 0$ with $\Lambda v\ge \rho v$; normalize it so ${\max }_i{v}_i=1$. For sufficiently small $\eta >0$,For example any $0<\eta \le \min (1,2(\rho -1)/{\rho }^2)$ works. Coordinates with $v_i=0$ satisfy the inequality automatically. Starting at $x_0=\eta v$, iterate $x_{t+1}=T(x_t)$. Monotonicity makes the sequence increase, and $T$ takes nonnegative vectors into $[0,1{]}^l$, so it converges to a fixed point $x_{\infty }\ge \eta v\ne 0$. Part (a) gives $p\ge x_{\infty }$, proving survival from at least one type. This proves the spectral survival criterion for multitype Poisson branching for reducible as well as irreducible reproduction matrices.

There are genuine normalization inconsistencies in this PDF. In the standard linearized chord diagram model $G_n^{(1)}$, time $n$ gives $n$ edges and total vertex degree $2n$, with self-loops counted twice. The paper calls $2n$ the number of edges. Its right-endpoint hint also uses $\sqrt{i/(2n)}$ rather than $\sqrt{i/n}$. These cannot both describe the standard model; part (c)'s exponent is consequently inconsistent as well. We give the definition, prove the alternative construction and its limits, and explicitly identify the corrected conclusion rather than infer an invalid constant from the printed hint.

Start from the empty graph at time zero, or from one vertex with one self-loop at time one. To obtain $G_t$ from $G_{t-1}$, add vertex $t$ and an edge directed from $t$ to $I_t$, whereA self-choice creates a self-loop. The old vertex degrees sum to $2(t-1)$, so these probabilities sum to one. This is exact preferential attachment, including the outward half of the new edge as weight one for the new vertex; it is not a rule normalized by $2t$ or a process adding two edges at each step. The degree of a vertex here is its total incoming plus outgoing vertex degree. The construction in part (a) has exactly one chord per vertex and makes the edge-count discrepancy explicit.

Draw $n$ independent pairs of independent uniform random variables on $[0,1]$. In each pair call the minimum $L$ and maximum $R$, then relabel whole pairs so $R_1<\cdots <R_n$. Merge all endpoints in $(R_{i-1},R_i]$ into vertex $i$, with $R_0=0$, and join the blocks containing the two endpoints of each pair, orienting from the right endpoint to the left. Self-loops are retained. This gives the uniform linearized chord diagram representation.

Before ordering, a pair has joint density $2$ on $0<L<R<1$. Consequently its maximum has distribution $\mathrm{Pr}(R\le r)=r^2$ and density $2r$; conditional on $R=r$, its minimum is uniform on $[0,r]$. Independence and relabelling give the equivalent precise descriptionEvery one of the $(2n)!$ relative orderings of the independently drawn labelled endpoints has the same probability. After forgetting pair labels and within-pair labels, each matching of $2n$ ordered points is produced by $2^{n}n!$ orderings. Thus its matching is uniform among the $(2n-1)!!$ pairings.

To prove equivalence with the recursive graph law, remove the last endpoint and its mate from a uniform pairing. The remaining ordered points have a uniform $(n-1)$-pairing, and the mate's old rank is uniform among the $2n-1$ possible ranks, independently of that smaller pairing. Conversely insert the mate into a uniformly chosen one of its $2n-1$ gaps, and pair it with the new final endpoint. For each old vertex block, the number of gaps assigned to it is exactly the number of endpoints already in that block, hence its old total vertex degree. These are the gaps immediately before each endpoint of that block. The last gap, after the last old endpoint, makes both new endpoints belong to the new final block and produces a self-loop. Therefore the attachment probabilities are $d_i/(2n-1)$ for old vertices and $1/(2n-1)$ for the new one. Induction proves the continuous construction and the recursive LCD model have the same distribution. Inserting a left endpoint into an old block raises exactly that vertex's vertex degree without splitting any old block.

The first right endpoint is the smallest of $n$ independent pair maxima. A maximum exceeds $r$ with probability $1-r^2$, so for $0\le x\le \sqrt{n}$,Taking the limit gives the requested, correctly normalized resultThus $\sqrt{n}{R}_1$ converges to a continuous nonnegative limit $W$ with survival function $\mathrm{Pr}(W\ge x)=e^{-x^2}$. In particular the scaled first right endpoint is tight. This calculation uses maxima of pairs, not the first order statistic of all $2n$ individual endpoints, which would have a different scale. The converted TeX loses the formula in this part; the displayed limit has been recovered directly from the PDF.

First prove the concentration statement with its correct scale. Let $U_i=R_i^2$, the $i$th uniform order statistic. The number of sample points at most $z$ is $B_z\sim \mathrm{Bin}(n,z)$. Therefore $U_i>z$ means $B_z<i$, and $U_i<z$ means $B_z\ge i$, up to probability-zero ties. Take ${\epsilon }_n=1/\log n$ and $M=\lceil n^{1/10}\rceil$. Applying Chernoff bounds at $z=(1\pm {\epsilon }_n{)}^{2}i/n$ gives, for an absolute $c_0>0$ and sufficiently large $n$,When the upper endpoint exceeds one its upper-tail event is empty. A union bound makes the total failure probability for all $M\le i\le n$ at most $2n\exp (-c_{0}M/(\log n{)}^2)=o(1)$. On this event,where integral comparison gives ${\sum }_{i=M}^n{i}^{-1/2}=2\sqrt{n}+O(\sqrt{M})$.

The first vertex block has right endpoint $R_1$ and always contains $L_1$, so its initial chord contributes vertex degree two. All its other endpoints are those $L_i$ with $i\ge 2$ that fall below $R_1$. Conditional on the right endpoints, these events are independent with probabilities $R_1/R_i$. ThusThe fewer than $M$ early summands contribute at most $M=o(\sqrt{n})$ to this conditional mean. For the rest, the uniform estimate and uniform tightness of $\sqrt{n}{R}_1$ giveTo control the actual fluctuations without assuming unconditional independence, restrict to the concentration event and $\sqrt{n}{R}_1\le A$. Then $\mu (R)\le M+2+CA\sqrt{n}$. Conditional Chebyshev inequality bounds the probability of a deviation exceeding $\eta \sqrt{n}$ by $(M+2+CA\sqrt{n})/({\eta }^{2}n)=o(1)$. The discarded endpoint event has limiting probability $e^{-A^2}$; let $A\to \infty$. ThereforeSince $W$ has a continuous distribution, the corrected first-vertex degree in the LCD model tail isThis disproves the printed exponent $-y^2/8$ for $G_n^{(1)}$. The hint's factor is independently contradicted at $i=n$: its proposed upper bound tends to $1/\sqrt{2}$, whereasThus the printed concentration event has probability tending to zero, not one. Replacing its $2n$ by $n$ leads to the proven exponent $-y^2/4$. The exponent $-y^2/8$ would instead arise for $d_1(2n)/\sqrt{n}$, but then the graph has $2n$ vertices and the part (b) endpoint limit at $x/\sqrt{n}$ becomes $e^{-2x^2}$. It cannot repair all the printed claims with one convention. The literal part (c) is false for the named model; the full corrected limit and the source of the discrepancy are established above.