On a random graph with immigrating vertices: Emergence of the giant component
✍ Scribed by David J. Aldous; Boris Pittel
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 186 KB
- Volume
- 17
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
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ős-Ré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 = π/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 Smoluchowsky-type equations. The approximation allows us to apply results of Aldous [Brownian excursions, critical random graphs and the multiplicative coalescent, Ann Probab 25 (1997), 812-854] on emergence of giant components in the multiplicative coalescent, i.e., a nonuniform random graph process.