1
$\begingroup$

Consider Gilbert graph model $G(n, p)$ where $n$ is the number of vertices and $p$ is the probability that a directed edge $e$ connects two vertices $u$ and $v$. Let $G = (V, E)$ denote an arbitrary resulting graph.

The SCC graph $G^{SCC} = (V^{SCC}, E^{SCC})$ consists of an vertex for each strongly connected component (SCC) in $G$ and an edge $(u, v) \in E^{SCC}$ if there is any vertex in the SCC represented by $u$ which is connected with any vertex in the SCC represented by $v$ by an edge in $E$. It's easy to prove that $G^{SCC}$ is a DAG, i.e. all SCC's in $G^{SCC}$ are single vertices.

Question:

Is there some good upper bound on the expected number of vertices in $G^{SCC}$?

It should only depend on $n$ and $p$, but if a solution in the Erdös-Renyi-model $G(n, m)$ is easier, it may also be helpful. Here, $n$ vertices are given and one generates exactly $m$ edges with equal probability.

Approach: I am only able to get a constant factor (if $p$ is assumed to be constant). We can make $\lfloor n/2 \rfloor$ disjoint pairs of vertices in $V$. For each pair, the probability of forming a $2$-cycle is $p^2$. Thus, we have at least an expected number of $\displaystyle p^2 \left\lfloor \frac{n}{2} \right\rfloor$ such $2$-cycles each contributing at most one vertex to $V^{SCC}$. Thus, there are at most $\displaystyle n - 2p^2 \left\lfloor \frac{n}{2} \right\rfloor$ vertices in $G^{SCC}$ expected.

I'm sure that a much better bound can be obtained. Any help is appreciated.

$\endgroup$
0
$\begingroup$

If $p$ is assumed to be constant, then the probability of there being more than one vertex in $G^{SCC}$ is exponentially small.

Here's a quick argument for that. Let $v,w$ be any two vertices in the directed random graph. The probability that there is no directed path of length $2$ from $v$ to $w$ is $(1 - p^2)^{n-2}$: there are $n-2$ possible paths, and each of them appears with probability $p^2$. There are $n(n-1)$ ordered pairs of vertices $(v,w)$, so by the union bound, the probability is at most $$ n(n-1)(1-p^2)^{n-2} $$ that any two vertices are in different strongly connected components. So we can bound the expected number of components by $$ 1 + n(n-1)^2(1-p^2)^{n-2} $$ which is exponentialy close to $1$: unless an event with probability $n(n-1)(1-p^2)^{n-2}$ happens, there is only one component, and even if it does there are at most $n$.


For most sparse random graphs (with $p$ a decaying function of $n$) I would expect the random directed graph to behave similarly to the undirected case. That is:

  • At a threshold of $p = \frac{\log n}{n}$ or so, the graph becomes strongly connected; shortly before this threshold, there is a giant component and a few components of size $1$, which follow a Poisson distribution. This should tell you the expected number of components.
  • When $p = \frac cn$, for $c>1$ (probably?) there is a linear-size giant strongly-connected component, and other components are logarithmic. So the expected number of components is $O(\frac{n}{\log n})$?

For $p$ even smaller than this, the two models should be different. The undirected random graph has $n-m$ components when it has $m$ edges, for small values of $m$, but the number of components in the directed random graph should stay close to $n$ because cycles are hard to come by.

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