2
$\begingroup$

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 ?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – François G. Dorais
    Commented May 27, 2013 at 17:25
  • 7
    $\begingroup$ 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. $\endgroup$
    – j.c.
    Commented May 27, 2013 at 17:54

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – j.c.
    Commented May 28, 2013 at 13:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .