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₁,C₂,...) of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. The convergence occurs the sense of an L¹ 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₁,C₂,...) contains only finitely many components which are not loops.

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr