Erdős-Rényi model, network reliability

72 Views Asked by At

I recently came across the Erdős-Rényi model random graph model, which indeed fascinated me with its beauty and simplicity. I've started to dig into it and saw the following theorem (listed on Wiki, for instance):

Let $G(n, p)$ be a random graph containing $n$ vertices, then the following holds, for $p=\cfrac{c\cdot \log{n}}{n}$:

  • if $c > 1$, then graph will asymptotically almost surely be connected;
  • if $c < 1$, then graph will asymptotically almost surely have some isolated vertices and asymptotically almost surely be disconnected

The question is, what can we say about $c=1$? Is there anything interesting to say about this parameter value?

I would appreciate any response.

1

There are 1 best solutions below

0
On

When $$ p=\frac{\ln n}{n}+\frac{s+o(1)}{n} $$ for some fixed $s\in \mathbb{R}$, $$ \mathsf{P}(G(n,p)\text{ is connected})\to e^{-\exp(-s)}. $$ (see, e.g., Theorem 7.3 here).