Premium
On a random graph with immigrating vertices: Emergence of the giant component
Author(s) -
Aldous David J.,
Pittel Boris
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200009)17:2<79::aid-rsa1>3.0.co;2-w
Subject(s) - coalescent theory , mathematics , combinatorics , multiplicative function , giant component , random graph , bounded function , martingale (probability theory) , branching process , discrete mathematics , graph , statistics , mathematical analysis , biochemistry , chemistry , gene , phylogenetic tree
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. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 79–102, 2000