Let $G \sim D(n,p)$ be a directed random graph with $n$ vertices and the probability $p$ that there is a directed edge between any ordered pair of vertices.

Strong connectivity is the property that any pair of vertices are connected with a path of edges in both directions. It is known that a threshold for this property is $$\hat{p}_n=\frac{\log n}{n},$$ which means that if $\frac{p_n}{\hat{p}_n}\to 0$ (resp. $\infty$) then the probability that $G\sim D(n,p_n)$ be strongly connected tends to $0$ (resp. $1$). (See here)

As a consequence, if $0<p<1$ is fixed, then with high probability, $G$ is strongly connected. I would like to know if the convergence speed of this probability to $1$ is known. For example, in the non-directed case, the probability is equivalent to $1-n(1-p)^{n-1}$. (See here)

My goal would be to apply the Borel-Cantelli lemma to show that a.s., for sufficiently large $n$, $G$ is strongly connected.

  • $\begingroup$ I'm not sure why $G$ would be strongly connected for sufficiently large $n$ - if this isn't the case for undirected graphs, wouldn't it be harder for directed graphs? I'm not sure though, and I would really like to know the answer, so I started a bounty on this question. $\endgroup$ – wythagoras Aug 20 '16 at 11:39
  • $\begingroup$ Well, it is the case for undirected graphs, since the probability that $G$ is not connected is equivalent to $n(1-p)^{n-1}$ when $p$ is constant, which is summable. $\endgroup$ – T Gerard Aug 22 '16 at 11:54

Your Answer

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

Browse other questions tagged or ask your own question.