The scaling limit of a critical random directed graph

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 gi...

Täydet tiedot

Bibliografiset tiedot
Päätekijät: Goldschmidt, C, Stephenson, R
Aineistotyyppi: Journal article
Kieli:English
Julkaistu: Institute of Mathematical Statistics 2023
_version_ 1826309865065152512
author Goldschmidt, C
Stephenson, R
author_facet Goldschmidt, C
Stephenson, R
author_sort Goldschmidt, C
collection OXFORD
description 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.
first_indexed 2024-03-07T07:42:05Z
format Journal article
id oxford-uuid:2fd40076-182e-4e26-aa55-6b17ef8683f1
institution University of Oxford
language English
last_indexed 2024-03-07T07:42:05Z
publishDate 2023
publisher Institute of Mathematical Statistics
record_format dspace
spelling oxford-uuid:2fd40076-182e-4e26-aa55-6b17ef8683f12023-05-04T13:42:41ZThe scaling limit of a critical random directed graphJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:2fd40076-182e-4e26-aa55-6b17ef8683f1EnglishSymplectic ElementsInstitute of Mathematical Statistics2023Goldschmidt, CStephenson, RWe 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.
spellingShingle Goldschmidt, C
Stephenson, R
The scaling limit of a critical random directed graph
title The scaling limit of a critical random directed graph
title_full The scaling limit of a critical random directed graph
title_fullStr The scaling limit of a critical random directed graph
title_full_unstemmed The scaling limit of a critical random directed graph
title_short The scaling limit of a critical random directed graph
title_sort scaling limit of a critical random directed graph
work_keys_str_mv AT goldschmidtc thescalinglimitofacriticalrandomdirectedgraph
AT stephensonr thescalinglimitofacriticalrandomdirectedgraph
AT goldschmidtc scalinglimitofacriticalrandomdirectedgraph
AT stephensonr scalinglimitofacriticalrandomdirectedgraph