2
$\begingroup$

Suppose $G$ is a random simple graph, that has $n$ vertices, and edges, that are present independently with probability $p$. What is the probability of $G$ being connected?

It is quite easy to calculate the probability for small $n$ (as for small $n$ we can classify all connected graphs with $n$ vertices). Thus for $n = 1$ the probability is $1$, for $n = 2$ it is $p$, and for $n = 3$ it is $3p^2 - 2p^3$. However, I do not know, how to calculate it for arbitrary $n$.

Any help will be appreciated.

$\endgroup$
  • $\begingroup$ This might be the same question. I am not sure yet, though. $\endgroup$ – drhab Jun 5 '18 at 15:09
  • 1
    $\begingroup$ Calculating the exact probability that it is connected is probably hopeless, and wouldn't tell you very much anyway. More accessible is asymptotic behavior as $n \to \infty$, for example at what critical probability $p = f(n)$ the graph switches from being a.s. disconnected to a.s. connected. See, for example, en.wikipedia.org/wiki/Giant_component. $\endgroup$ – Qiaochu Yuan Jun 5 '18 at 15:39