[Math] the expected size of the largest strongly connected component of a graph

Question

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?

Answer 1

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.