Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs (Q2818275)

This paper is a contribution to the theory of giant components in random digraphs. Two models, \(D(n,p)\) where there are \(n\) labelled vertices and each of the \(n(n-1)\) possible arcs (directed edges) arises with probability \(p\) independent of all other directed edges, and \(D(n,m)\) where again there are \(n\) labelled vertices and \(m\) arcs in total. The theory of these two models for values of \(m\) close to \(pn(n-1)\) are, unsurprisingly, closely related.NEWLINENEWLINEIt has long been known, through independent work of \textit{R. M. Karp} [Random Struct. Algorithms 1, No. 1, 73-93 (1990; Zbl 0712.68076)] and \textit{T. Łuczak} [J. Graph Theory 14, No. 2, 217--223 (1990; Zbl 0712.05051)], that if \(m=cn\) for a constant \(c>1\) then there is a unique strong component whose order is linear in the number of vertices \(n\) -- this is broadly similar to the emergence of a ``giant component'', in an undirected graph. Further its size is asymptotically \(\theta^{2}n\) where \(\theta\) is the unique positive root of \(1-\theta=e^{-\theta c}\).NEWLINENEWLINEThe substantial paper under review proves that, in both random digraph models, the joint distribution of the number of vertices and the number of arcs in the giant strong component is asymptotically Gaussian, with a certain well-understood mean vector (the same in both models) and two covariance matrices (which are slightly different in the two models).NEWLINENEWLINEThe proof proceeds by analysing a randomized deletion process which terminates in the maximal subgraph with minimum indegree and minimum outdegree at least 1 -- this (the ``(1,1) core'') of course must contain all non-trivial strong components. The authors show that the number of ``peripheral'', vertices and arcs in the (1,1) core, i.e. those not in the largest strong components, are at most a poly-logarithmic function of \(n\) in number and so are swamped by the order of magnitude \(n^{1/2}\) fluctuations that one would expect in the size of the giant strong component. The detailed proof techniques include supermartingales and some partial differential equations.