# Upper Bound on Vertices in SCC Graph of Directed Random Graph

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.

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.