A Random Graph Growth Model

DOI10.1112/BLMS.12957MaRDI QIDQ6508483arXivFDO

Authors Michael Farber, Alexander Gnedin, Wajid H. Mannan

Published in arXiv

Full work available at URL https://doi.org/10.1112/BLMS.12957

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20)

Abstract: A growing random graph is constructed by successively sampling without replacement an element from the pool of virtual vertices and edges. At start of the process the pool contains $N$ virtual vertices and no edges. Each time a vertex is sampled and occupied, the edges linking the vertex to previously occupied vertices are added to the pool of virtual elements. We focus on the edge-counting at times when the graph has $nleqN$ occupied vertices. Two different Poisson limits are identified for $nasymp{N}^{1/3}$ and $N-nasymp1$. For the bulk of the process, when $nasympN$, the scaled number of edges is shown to fluctuate about a deterministic curve, with fluctuations being of the order of $N^{3/2}$ and approximable by a Gaussian bridge.

This page was built for publication: A Random Graph Growth Model

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