THE SCALING LIMIT OF A CRITICAL RANDOM DIRECTED GRAPH

• 成果类型: Article
• 署名作者: Goldschmidt, Christina; Stephenson, Robin
• 署名单位: University of Oxford; University of Sheffield
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1859
• 发表日期: 2023
• 页码: 2024-2065
• 关键词: trees

摘要

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 + lambda n-4/3 for lambda e 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 (C-1, C-2, ...) 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 Erdos-Renyi 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. If we ignore the edge lengths, any fixed finite sequence of 3-regular strongly connected directed multigraphs occurs with positive probability.