= Solution
Explore the <connected component of a graph> containing a fixed vertex $v$ by <Breadth-first search>. If the exploration discovers at least $m$ vertices, then before its $m$th discovery at least $m-1$ of at most $mn$ tested potential edges must be present. The tests are independent Bernoulli trials with parameter $p=(1-\varepsilon)/n$, so
$$
\mathbb P(|C(v)|\geq m)
\leq
\mathbb P(\operatorname{Bin}(mn,p)\geq m-1).
$$
The <binomial distribution> on the right has mean $(1-\varepsilon)m$. For $m\geq2/\varepsilon$, the <exponential Markov bound> gives
$$
\mathbb P(|C(v)|\geq m)\leq e^{-c\varepsilon^2m}
$$
for an absolute constant $c>0$. The <union bound> over the $n$ choices of $v$ now gives
$$
\mathbb P\left(\max_v|C(v)|\geq m\right)
\leq ne^{-c\varepsilon^2m}.
$$
Taking $m=C_\varepsilon\log n$ with $C_\varepsilon>2/(c\varepsilon^2)$ makes this probability tend to zero. This proves the <subcritical component bound for a binomial random graph>.
Back to article page
