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.

  • $\begingroup$ $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)$. $\endgroup$ – Aryabhata Apr 12 '13 at 1:14
  • $\begingroup$ I take it you've seen the results for large $p$ here en.wikipedia.org/wiki/Erdos-Renyi_model ? $\endgroup$ – muzzlator Apr 12 '13 at 1:21
  • 2
    $\begingroup$ For constant $p$, the wikipedia page implies that your graph is almost surely connected as $n\rightarrow \infty$. $\endgroup$ – EuYu Apr 12 '13 at 1:26
  • $\begingroup$ @Aryabhata You're probably thinking of $np$ being constant. $\endgroup$ – Erick Wong Apr 12 '13 at 1:29
  • $\begingroup$ @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)$. $\endgroup$ – Aryabhata Apr 12 '13 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.