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 $n\leq N$ occupied vertices. Two
different Poisson limits are identified for $n\asymp N^{1/3}$ and $N-n\asymp
1$. For the bulk of the process, when $n\asymp N$, 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.