Timeline for Random graphs require O(n log(n)) edges until they are almost certainly fully connected - what are more concrete boundaries ?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 25, 2013 at 3:02 | review | First posts | |||
| Jun 25, 2013 at 11:54 | |||||
| May 28, 2013 at 11:12 | answer | added | Goldstern | timeline score: 1 | |
| May 27, 2013 at 17:54 | comment | added | j.c. | The connectivity transition is addressed in the first paper of Erdos and Renyi on random graphs (accessible here): renyi.hu/~p_erdos/1959-11.pdf . Briefly: if you have added $n/2(\log n+c)$ edges to the graph, the probability that the graph is connected is (as $n\rightarrow\infty$) $e^{-e^{-c}}$. Near the transition you essentially have one giant component and a bunch of isolated vertices. | |
| May 27, 2013 at 17:43 | answer | added | Chassaing | timeline score: 2 | |
| May 27, 2013 at 17:25 | comment | added | François G. Dorais | This is a 0-1 law so I don't think there is such a $c$, unless I'm misunderstanding the question. In any case, a good reference is Joel Spencer's The Strange Logic of Random Graphs. | |
| May 27, 2013 at 17:13 | history | asked | tdullien | CC BY-SA 3.0 |