The critical window in random digraphs

Abstract

We consider the component structure of the random digraph $D(n,p)$ inside the critical window $p=n^{-1}+\lambda n^{-4/3}$.We show that the largest component ${\mathcal{C}}_1$ has size of order $n^{1/3}$ in this range. In particular we give explicit bounds on the tail probabilities of $|{\mathcal{C}}_1|n^{-1/3}$.

21 pages