1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Took an entire mathematics for computer science(discrete mathematics) course to understand this. Still not able to. $\endgroup$ – Sumeet Aug 7 '18 at 14:08
  • $\begingroup$ Unfortunately one course is not enough. You also need a thorough grounding in discrete probability theory. $\endgroup$ – Yuval Filmus Aug 7 '18 at 14:28
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.