| Summary: | We consider the random directed graph ⃗G(n,p) with vertex set {1,2,...,n}
in which each of the n(n − 1) possible directed edges is present indepen-
dently with probability p. We are interested in the strongly connected com-
ponents of this directed graph. A phase transition for the emergence of a
giant strongly connected component is known to occur at p = 1/n, with
critical window p = 1/n + λn−4/3 for λ ∈ R. We show that, within this
critical window, the strongly connected components of ⃗G(n,p), ranked in
decreasing order of size and rescaled by n−1/3, converge in distribution to a
sequence (C1,C2,...) of finite strongly connected directed multigraphs with
edge lengths which are either 3-regular or loops. The convergence occurs in
the sense of an ℓ1 sequence metric for which two directed multigraphs are
close if there are compatible isomorphisms between their vertex and edge
sets which roughly preserve the edge lengths. Our proofs rely on a depth-first
exploration of the graph which enables us to relate the strongly connected
components to a particular spanning forest of the undirected Erd˝os–Rényi
random graph G(n,p), whose scaling limit is well understood. We show that
the limiting sequence (C1,C2,...) contains only finitely many components
which are not loops. If we ignore the edge lengths, any fixed finite sequence
of 3-regular strongly connected directed multigraphs occurs with positive
probability.
|
|---|