What do the strongly connected components of a large directed graph with i.i.d. degree tuples look like?

Abstract

Universal scaling limits of random graph models can be considered the Central Limit Theorems of graph theory and have attracted a lot of interest in recent years. We consider the strongly connected components (SCC) of a uniform directed graph on $n$ vertices with i.i.d. degree tuples, under suitable moment conditions on the degree distribution. The moment conditions ensure that the graph is critical: the largest SCC contains O(n^{1/3}) vertices, and there are many other SCC of that order. We show that the sequence of SCC ordered by decreasing length converges under rescaling of the edge lengths to a random sequence of directed multigraphs with edge lengths that are all 3-regular or loops. The talk is based on joint work with Zheneng Xie.