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

DOI10.1002/RSA.20622MaRDI QIDQ2818275zbMATH OpenOpenAlexFDO

Authors Boris Pittel, Daniel Poole

Publication date 7 September 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.4022

zbMATH Keywords

central limit theoremcoregiant componentrandom digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Abstract: Two models of a random digraph on $n$ vertices, $D(n,extProb(extarc)=p)$ and $D(n,extnumberofarcs=m)$ are studied. In 1990, Karp for $D(n,p)$ and independently T. L uczak for $D(n,m=cn)$ proved that for $c>1$, with probability tending to 1, there is an unique strong component of size of order $n$. Karp showed, in fact, that the giant component has likely size asymptotic to $nhet{a}^2$, where $heta=heta(c)$ is the unique positive root of $1-heta=e^{-cheta}$. In this paper we prove that, for both random digraphs, the joint distribution of the number of vertices and number of arcs in the giant strong component is asymptotically Gaussian with the same mean vector $$, $$ and two distinct $2imes2$ covariance matrices, $nmathbfB(c)$ and $$. To this end, we introduce and analyze a randomized deletion process which determines the directed $(1,1)$-core, the maximal digraph with minimum in-degree and out-degree at least 1. This $(1,1)$-core contains all non-trivial strong components. However, we show that the likely numbers of peripheral vertices and arcs in the $(1,1)$-core, those outside the largest strong component, are of log-polynomial order, thus dwarfed by anticipated fluctuations, on the scale of $n^{1/2}$, of the giant component parameters. By approximating the likely realization of the deletion algorithm with a deterministic trajectory, we obtain our main result via exponential supermartingales and Fourier-based techniques.

Recommendations

• The strong giant in a random digraph
• On tree census and the giant component in sparse random graphs
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• On the largest strong components in m-out digraphs
• The Strongly Connected Components of 1-in, 1-out

Cites work

• scientific article; zbMATH DE number 5819433 (Why is no real title available?)
• scientific article; zbMATH DE number 3878944 (Why is no real title available?)
• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• An urn model for cannibal behavior
• Anatomy of a Young giant component in the random graph
• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums
• Asymptotic enumeration of strongly connected digraphs by vertices and edges
• Asymptotic normality of the \(k\)-core in random graphs
• Asymptotic normality of the size of the giant component in a random hypergraph
• Asymptotic normality of the size of the giant component via a random walk
• Component behavior near the critical point of the random graph process
• Component sizes of the random graph outside the scaling window
• Counting connected graphs inside-out
• Counting strongly-connected, moderately sparse directed graphs
• Large‐deviations/thermodynamic approach to percolation on the complete graph
• Local limit theorems for the giant component of random hypergraphs
• Normal convergence problem? Two moments and a recurrence may be the clues
• On the Probability of Connectedness of a Random Graph $\mathcal{G}_m (t)$
• On the fluctuations of the giant component
• On the normality of giant components
• On tree census and the giant component in sparse random graphs
• Random dense bipartite graphs and directed graphs with specified degrees
• Stable husbands
• Sudden emergence of a giant k-core in a random graph
• The Evolution of Random Graphs
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The critical behavior of random digraphs
• The order of the giant component of random hypergraphs
• The phase transition in a random hypergraph
• The phase transition in random graphs: a simple proof
• The phase transition in the evolution of random digraphs
• The random bipartite nearest neighbor graphs
• The transitive closure of a random digraph

Cited in

(12)

• Counting directed acyclic and elementary digraphs
• Percolation in simple directed random graphs with a given degree distribution
• The critical beta-splitting random tree. I: Heights and related results
• On the largest strong components in m-out digraphs
• The giant component of the directed configuration model revisited
• Birth of a strongly connected giant in an inhomogeneous random digraph
• The distribution of the relative arc density of a family of interval catch digraph based on uniform data
• The strong giant in a random digraph
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The critical behavior of random digraphs
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
• The birth of the strong components

This page was built for publication: Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2818275)