Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 22 octobre 2019 à 10h00 en Amphi Darwin, Robin Stephenson nous parlera de : The scaling limit of a critical random directed graph

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

Dernière modification : Friday 18 October 2019 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at