1
$\begingroup$

Given a directed graph with n vertices and the probability of any edge existing being p, what is the size of the largest strongly connected component in the graph? What if its undirected graph? Can we also estimate the number of components too in terms of n and p?

$\endgroup$
4
$\begingroup$

Much is known about the behavior of the (undirected) random graph $G(n, p)$ in the Erdős–Rényi model, including the following:

$\langle$Begin quote$\rangle$

  • If $np < 1$, then a graph in $G(n, p)$ will almost surely have no connected components of size larger than $O(\log(n))$.

  • If $np = 1$, then a graph in $G(n, p)$ will almost surely have a largest component whose size is of order $n^{2/3}$.

  • If $np → c > 1$, where $c$ is a constant, then a graph in $G(n, p)$ will almost surely have a unique giant component containing a positive fraction of the vertices. No other component will contain more than $O(\log(n))$ vertices.

  • If $p<\tfrac{(1-\epsilon)\ln n}{n}$, then a graph in $G(n, p)$ will almost surely contain isolated vertices, and thus be disconnected.

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

  • Thus $\tfrac{\ln n}{n}$ is a sharp threshold for the connectedness of $G(n, p)$.

$\langle$End quote$\rangle$

The directed case is studied here.

$\endgroup$
  • $\begingroup$ Quote: What if its undirected graph? // About the directed case: do you decide the existence of edge $xy$ and the existence of edge $yx$ independently? $\endgroup$ – Did Apr 7 '13 at 13:03
  • $\begingroup$ See the last line of my answer. $\endgroup$ – Did Apr 7 '13 at 13:27
  • $\begingroup$ (Previous two comments answering now-deleted queries by the OP.) $\endgroup$ – Did Apr 7 '13 at 20:37
1
$\begingroup$

The random directed graph on $n$ vertices, where each potential arc is present with probability $p$ independent of any other arc is typically denoted by $D(n,p)$. As Did's link mentions, $p=\ln n/n$ is a sharp threshold for strong connectedness. The following results deal with sparse random digraphs.

A $complex$ strong component is a strong component with more arcs than vertices. In other words, a complex strong component is a strong component that is neither a single vertex or a cycle.

Karp (1990, "The transitive closure of a random digraph") and Luczak (1990, "The phase transition in the evolution of random digraphs") proved that for any $\omega(n)$ tending to $\infty$, with probability tending to 1,

1) each strong component of $D(n,p=c/n), c<1$ has size less than $\omega$ and there are no complex strong components.

2) there is an unique complex strong component in $D(n,p=c/n),c>1$ which is of size on the order of $n$, and each other strong component has size less than $\omega$.

As opposed to undirected random graphs, this $\omega$ can tend to $\infty$ however slowly!

The behavior of $D(n,p=1/n)$ has been difficult to establish. As far as I know, the most up to date information, proved by Luczak and Seierstad (2009, "The Critical Behavior of Random Digraphs"), is that there is some $a,b \in (0,1)$ such that for $n$ large enough

$$P(\text{there exists a complex component in }D(n,p=1/n)) \in [a,b]$$

In the same paper, they show analogous results to 1) and 2) above for $c$ tending to 1, but $n^{1/3}|c-1| \to \infty$.

$\endgroup$

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.