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≍N1/3 and N−n≍1. For the bulk of the process, when n≍N, the normalised number of edges is shown to fluctuate about a nonrandom curve, with fluctuations being of the order of N3/2 and approximable by a Gaussian bridge. This is a joint work with Michael Farber and Wajid Mannan.