# 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}$$.

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