# What can be said about the number of connected components of $G(n,p)$ random graphs?

By a $G(n,p)$ graph we mean a graph on $n$ vertices, all possible edges are independently included randomly with probability $p$.

What can be said about the number of connected components? For example, bounds or asymptotic behavior of the expected number of components as $n\rightarrow \infty$ or for $p$ close to 1.

• $p$ is constant? The wiki page has something: en.wikipedia.org/wiki/…, which seems to imply that the expected number for constant $p$ will be $\Omega(n/\log n)$. – Aryabhata Apr 12 '13 at 1:14
• I take it you've seen the results for large $p$ here en.wikipedia.org/wiki/Erdos-Renyi_model ? – muzzlator Apr 12 '13 at 1:21
• For constant $p$, the wikipedia page implies that your graph is almost surely connected as $n\rightarrow \infty$. – EuYu Apr 12 '13 at 1:26
• @Aryabhata You're probably thinking of $np$ being constant. – Erick Wong Apr 12 '13 at 1:29
• @ErickWong: No, I was thinking of the case $np \to \infty$, where there is one giant component, and the remaining components are of size $O(\log n)$. – Aryabhata Apr 12 '13 at 3:54