Scaling limist of critical directed graphs

Thesis

The scaling limit of connected components in critical undirected random graphs has been well studied and shown to be universal between different critical models of undirected random graphs. Work by Goldschmidt and Stephenson has established the scaling limit of a the strongly connected components of critical directed Erdös-Rényi random graphs.

We investigate whether the same scaling limits arise in different critical models of random directed graphs. We study two models in particular: the directed configuration model and inhomogeneous directed random graphs. Our first main result is a scaling limit for the strongly connected components in a critical directed configuration model. Our proofs rely on two main in- gredients: a depth first exploration of the directed configuration model to construct an out-forest for the model and also the identification of a distinguished subset of edges not in the out-forest, called candidates, which are the only edges not in the out-forest which can be part of a strongly connected component. The number of such candidate edges remains bounded asymptotically and will converge to point identifications on the real trees that arise as the scaling limits of the out-forests. We can then extract a directed multigraph with edge lengths by taking the root of each real tree and the point identifications, then orienting each edge away from the root. From these multigraphs, we can extract the con- tinuum strongly connected components. We also present work in progress on establishing a similar scaling limit for a family of rank-1 inhomogeneous random directed Poissonian graphs. We use similar techniques to the directed configuration model but use a coupling with a queueing process instead to construct an out-forest.

Authors: Xie, Z

• DOI: 10.5287/ora-xomgzbopd
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: IRDGs; random graphs; directed graphs; scaling limits; inhomegeneous directed random graphs; directed configuration model
• Subjects: Limit theorems (Probability theory); Directed graphs; Graph theory