# Critical probability for Erdos-Renyi digraphs to be strongly connected

Given $$p \in [0,1]$$, an Erdos-Renyi graph $${ER}(n,p)$$ on $$n$$ vertices is constructed by defining, for each unordered couple of distinct vertices $${i,j}$$ an edge between $$i$$ and $$j$$ with probability $$p$$.

Similarly we define an Erdos-Renyi digraph, which we shall denote as $${ER}_d(n,p)$$, on $$n$$ vertices by defining, for each ordered pair of distinct vertices $$(i,j)$$ an edge $$i \to j$$ with probability $$p$$.

Erdos and Renyi proved that $$p=\frac{\ln(n)}{n}$$ is a sharp threshold for the connectedness of an (undirected) E-R graph, that is :

• If $${\displaystyle p<{\tfrac {(1-\varepsilon )\ln n}{n}}}$$, then $${ER}(n,p)$$ will almost surely contain isolated vertices, and thus be disconnected.

• If $${\displaystyle p>{\tfrac {(1+\varepsilon )\ln n}{n}}}$$, then a graph $${ER}(n,p)$$ will almost surely be connected.

Is there a similar sharp bound for the strong connectedness of $${ER}_d(n,p)$$?

I collected statistics on $${ER}_d(n,p)$$ for $$n \le 300$$ and a resolution of $$0.02$$ for $$p$$, with $$200$$ generations for each $$(n,p)$$. I measure a critical probability for (almost sure) strong connectedness asymptotically close to $$p=\frac{2\ln(n)}{n}$$.

• onlinelibrary.wiley.com/doi/full/10.1002/… includes mention of sources that answer this question. Commented May 21, 2020 at 1:08
• @Brendan McKay: That resource is blocked for me, what is the answer they give? Commented May 21, 2020 at 1:12
• math.unl.edu/~xperezgimenez2/papers/dicores.pdf Commented May 21, 2020 at 2:09
• It’s the same threshold. As in the undirected caseIt’s more or less immediate to see that this condition is what you need not to have components of size 1. Commented May 21, 2020 at 2:11
• @AnthonyQuas Agreed if by "component" you mean "strong component". Commented May 21, 2020 at 6:39

Here's the MathSciNet summary of the paper: "Let $$G_{n,N}$$ be a random directed graph having $$n$$ vertices and $$N$$ directed edges, the edges being chosen from the $${n \choose 2}$$ possible edges so that each of the $${n^2\choose N}$$ possible choices is equiprobable (i.e., loops are allowed). Let $$P(n,N)$$ denote the probability that $$G_{n,N}$$ is strongly connected. Then if $$N_c"=[n\log n+cn]$$, where $$c$$ is an arbitrary fixed number and $$[x]$$ denotes the integral part of $$x$$, it is proved that $$\lim_{n \to \infty} P(n,Nc)=\exp(−2e−c)$$.