Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

As far as I understand my literature, the probability of a random graph being fully connected tends toward one as the number of edges approaches a value of size $O(n \log(n))$

The way I read this, there has to be some function $c:[0,1]\to \mathbb{R}$ so that for a given probability one obtains a constant factor for the $n \log(n)$.

More clearly: $c(p)$ should be the value so that after adding $c(p)n\log(n)$ edges the graph is fully connected with probability higher than $p$.

I'd imagine that tight bounds on / descriptions of $c$ are known, but I haven't found any in my (admittedly cursory) reading of the literature. Where should I look ?

share|improve this question
1  
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. –  François G. Dorais May 27 '13 at 17:25
7  
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. –  j.c. May 27 '13 at 17:54
add comment

2 Answers

according to the double exponential theorem of Erdos and Renyi, I would say that you need to add $(n \ln n)/2 + n Z_n /2$ edges in which $Z_n$ is a random variable that converges in distribution to the standard Gumbel distribution ... in my cursory reading (it needs to be checked and can be wrong, for you have to translate from the dynamic model with a random uniform weight on each edge to the dynamic model where you add one edge after the other).

share|improve this answer
add comment

Have you looked at "The birth of the giant component" by Svante Janson, Donald E. Knuth, Tomasz Łuczak, Boris Pittel? Available at arxiv.

Or at Joel Spencer's article on the golden anniversary of the giant component? Available at AMS.

share|improve this answer
3  
These articles discuss the phase transition of the formation of the giant component, which happens when the number of edges is near $n/2$. The full connectivity transition that this question is asking about occurs much later and is not quite related. –  j.c. May 28 '13 at 13:18
    
Thank you. I must have misremembered this paper. –  Goldstern May 30 '13 at 15:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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