Résumé : 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 independently with probability p. We are interested in the strongly connected components 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), rescaled by n^{-1/3}, converge in distribution to a sequence (C_{1},C_{2},...) of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. The convergence occurs the sense of an L^{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ős-Rényi random graph G(n,p), whose scaling limit is well understood. We show that the limiting sequence (C_{1},C_{2},...) contains only finitely many components which are not loops.
Dernière modification : Wednesday 12 October 2022 | Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |