On a Random Graph with Immigrating Vertices: Emergence of the Giant Component
David J. Aldous and Boris Pittel
A randomly evolving graph, with vertices immigrating at rate $n$ and
each possible edge appearing at rate $1/n$, is studied. The detailed
picture of emergence of giant components with $O(n^{2/3})$ vertices
is shown to be the same as in the Erd\H{o}s - R\'{e}nyi graph process
with the number of vertices fixed at $n$ at the start. A major difference
is that now the transition occurs about a time $t=\pi/2$, rather
than $t=1$. The proof has three ingredients. The size of the largest
component in the subcritical phase is bounded by comparison with a
certain multitype branching process. With this bound at hand, the growth
of the sum-of-squares and sum-of-cubes of component sizes is shown, via
martingale methods, to follow closely a solution of the Smoluchovsky-type
equations. The approximation allows us to apply results of Aldous (1997) on
emergence of giant components in the multiplicative coalescent, i.e. a
non-uniform random graph process.