Explanation about the condition for connectivity in Erdos Reyni model

Question

I am currently studying the Erdos-Reyni model, the $G(n,p)$ model to be specific.

Its easy to understand that all graphs with $m$ edges have generating probability of $p^{m}(1-p)^{n(n-1)/2 - m}$ where p is the probability that there is an edge between a pair of vertices.

What I am not able to understand is the following:

Almost every graph in $G(n, 2ln(n)/n)$ is connected. In other words, As $n$ tends to infinity, the probability that a graph on $n$ vertices with edge probability $p = 2ln(n)/n$ is connected, as $n$ gets very large.

Any idea how to get this?

Answer 1

If a graph is not connected then there must be a set $S$ of vertices not connected to its complement. Furthermore, we can assume that $|S| \leq n/2$. For a given set $S$, the probability that $S$ is not connected to its complement is $$ (1-p)^{|S|(n-|S|)} \leq e^{-p|S|(n-|S|)}. $$ The union bound shows that the probability that some such $S$ exists is at most $$ \epsilon := \sum_{k=1}^{n/2} \binom{n}{k} e^{-pk(n-k)} = \underbrace{\sum_{k=1}^{n/4} \binom{n}{k} e^{-pk(n-k)}}_{\epsilon_1} + \underbrace{\sum_{k=n/4+1}^{n/2} \binom{n}{k} e^{-pk(n-k)}}_{\epsilon_2}. $$ When $k \leq n/4$, we have $n-k \geq (3/4)n$ and so $$e^{-p(n-k)} \leq e^{-(3/4)pn} = \frac{1}{n^{3/2}}.$$ Using the bound $\binom{n}{k} \leq n^k$, we get $$ \epsilon_1 \leq \sum_{k=1}^{n/4} n^k \cdot n^{-(3/2)k} = \sum_{k=1}^{n/4} \frac{1}{n^{k/2}}. $$ We can estimate this by considering separately $k=1$, $k=2$, and $k \geq 3$: $$ \epsilon_1 \leq \frac{1}{\sqrt{n}} + \frac{1}{n} + \sum_{k=3}^{n/4} \frac{1}{n^{3/2}} \leq \frac{1}{\sqrt{n}} + \frac{1}{n} + \frac{n}{4} \cdot \frac{1}{n^{3/2}} = O\left(\frac{1}{\sqrt{n}}\right). $$ When $n/4 < k \leq n/2$, we have $n-k \geq n/2$ and so $e^{-p(n-k)} \leq e^{-pn/2} = 1/n$. Using the sharper upper bound $\binom{n}{k} \leq (\frac{en}{k})^k$, we get $$ \epsilon_2 \leq \sum_{k=n/4+1}^{n/2} \left(\frac{en}{k}\right)^k \cdot \frac{1}{n^k} = \sum_{k=n/4+1}^{n/2} \left(\frac{e}{k}\right)^k. $$ The summands $(e/k)^k$ are decreasing, and so $$ \epsilon_2 \leq \frac{n}{4} \left(\frac{4e}{n}\right)^{n/4} \leq \left(\frac{4e}{n}\right)^{n/4-1} = O\left(\frac{1}{\sqrt{n}}\right), $$ since when $n \geq 6$, the exponent is at least $1/2$.

Putting everything together, we get that the probability that the graph is not connected is at most $$ \epsilon = O\left(\frac{1}{\sqrt{n}}\right). $$

Using more refined arguments, one can show that when $p = \frac{\ln n + c}{n}$ for constant $c$, the probability that $G(n,p)$ is connected tends to $e^{-e^{-c}}$. Moreover, in a certain precise sense, the only obstacle to connectivity (whp) is isolated vertices.

Answer 2

Hint: Try to compute the probability of a node not connected to at least $\frac{n}{2}$ of vertices: $$P= (1-\frac{2\ln(n)}{n})^{n/2}$$ If $n$ goes to $\infty$, we have: $$P = \frac{1}{e^{\ln(n)}} = \frac{1}{n} \rightarrow0$$

Hence, the probability of each node is connected to at least $\frac{n}{2}$ of nodes goes to $1$. You can get help from this to proof the connectivity.