14:00
The scaling limit of a critical random directed graph
Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.
Abstract
We consider the random directed graph $D(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 \in \mathbb{R}$. We show that, within this critical window, the strongly connected components of $D(n,p)$, ranked in decreasing order of size and rescaled by $n-1/3$, converge in distribution to a sequence $(C_1,C_2,\ldots)$ of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. The convergence occurs in the sense of an $L^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ős-Rényi random graph $G(n,p)$, whose scaling limit is well understood. We show that the limiting sequence $(C_1,C_2,\ldots)$ 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.