The scaling limit of a critical random directed graph

Abstract: We consider the random directed graph $D(n, p)$ with vertex set $\{1, 2, \ldots, 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 \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 of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops.

This is joint work with Robin Stephenson (University of Sheffield).

Frenchprobability

Audience: researchers in the topic

Les probabilités de demain webinar

Series comments: There will be no seminar on 1st June because it is a public holiday in France (Pentecôte). The session on 15th June is the last one.