A Random Graph Growth Model
A growing random graph is constructed by successively sampling without replacement an element from the variable 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 it becomes occupied, and the edges linking the vertex to previously occupied vertices are added to the pool of virtual elements. Each time a virtual edge is sampled, it becomes occupied and is included in the graph. We focus on the edge-counting at times when the graph composed of occupied elements has $n≤N$ 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 normalised number of edges is shown to fluctuate about a nonrandom curve, with fluctuations being of the order of $N^{3/2}$ and approximable by a Gaussian bridge. This is a joint work with Michael Farber and Wajid Mannan.