2
$\begingroup$

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

enter image description here

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ well, the result in the paper summary is not what i measured. The critical probability for digraph follows from the argument by Erdos in the second paper you linked, however. $\endgroup$ – Joshua Benabou May 28 at 1:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.