Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / B / 7 / a / Solution

Explore the component of one vertex by processing discovered vertices in order. At each step, the number of newly discovered neighbours is a binomial variable with at most $n$ trials and success probability $1/(2n)$, on previously unexposed independent edges. Pad each step with independent dummy trials. This couples the exploration below independent offspring variables ${\xi }_i\sim \mathrm{Bin}(n,1/(2n))$, each of mean one half.

If the component has at least $k\ge 2$ vertices, after $k-1$ vertices have been processed at least $k-1$ offspring must have been found. HenceThe sum is binomial with mean $\mu =(k-1)/2$. The multiplicative Chernoff inequality $P(B\ge 2\mu )\le (e/4{)}^{\mu }$ therefore givesA union bound over all vertices bounds the probability of any component of size at least $k$ by $n{e}^{-c(k-1)}$. Taking $k=\lceil \alpha {\log }_{e}n\rceil$ with any $\alpha >1/c$, for example ten, makes this tend to zero. Thus the largest component is at most a constant times $\log n$ with high probability.