Critical probability for Erdos-Renyi digraphs to be strongly connected

Question

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

Answer 1

This is basically the main result of a paper by Ilona Palásti:

On the strong connectedness of directed random graphs. Studia Sci. Math. Hungar. 1 (1966), 205–214.

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

The result is extended from the directed model with a fixed number of edges to the binomial directed random graph, which I think is what you're asking about, in the paper "A note on thresholds and connectivity in random directed graphs", by Alasdair J. Graham and David A. Pike; you can find that here.