Connectivity threshold in the Erdős-Rényi model

For every fixed $\epsilon >0$,whereas the probability tends to zero when $p\le (1-\epsilon )\log n/n$. Above the threshold a union bound excludes every component of size at most $n/2$; below it isolated vertices remain with high probability.

A disconnected binomial random graph has a connected component of a graph with at most half its vertices. The union bound over its possible vertex sets givesThe final geometric series bound tends to zero for fixed $p>0$.

For fixed real $c$, the number of isolated vertices in a binomial random graph with $p=(\log n+c)/n$ converges to a Poisson distribution of mean $e^{-c}$. Its fixed factorial moments tend to $(e^{-c}{)}^k$. A union bound for small connected components, together with exclusion of intermediate components, shows that isolated vertices are asymptotically the only obstruction to connectivity. Thus the displayed limit is the zero-mass of that Poisson distribution.