# Random graphs require O(n log(n)) edges until they are almost certainly fully connected - what are more concrete boundaries ?

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 ?

• 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. Commented May 27, 2013 at 17:25
• 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.
Commented May 27, 2013 at 17:54

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).
• 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.