Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 12 / 1

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$.