- Main
On a random graph with immigrating vertices: Emergence of the giant component
Published Web Location
https://doi.org/10.1002/1098-2418(200009)17:2<79::aid-rsa1>3.0.co;2-wAbstract
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(n2/3) vertices is shown to be the same as in the Erdos-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.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
Enter the password to open this PDF file:
-
-
-
-
-
-
-
-
-
-
-
-
-
-