Paper Info
Title
The phase transition in the uniformly grown random graph has infinite order
Abstract
The aim of this paper is to study the emergence of the giant component in the uniformly grown random graph Gn(c), 0 c n] = {1, 2, …, n} in which each possible edge ij is present with probability c/ max{i, j}, independently of all other edges. Equivalently, we may start with the random graph Gn(1) with vertex set[n], where each vertex j is joined to each “earlier” vertex i j with probability 1/j, independently of all other choices. The graph Gn(c) is formed by the open bonds in the bond percolation on Gn(1) in which a bond is open with probability c. The model Gn(c) is the finite version of a model proposed by Dubins in 1984, and is also closely related to a random graph process defined by Callaway, Hopcroft, Kleinberg, Newman, and Strogatz [Phys Rev E 64 (2001), 041902]. Results of Kalikow and Weiss [Israel J Math 62 (1988), 257–268] and Shepp [Israel J Math 67 (1989), 23–33] imply that the percolation threshold is at c = 1/4. The main result of this paper is that for c = 1/4 + ε, ε 0, the giant component in Gn(c) has order exp(-&THgr;(1/√ ε)) n. In particular, the phase transition in the bond percolation on Gn(1) has infinite order. Using nonrigorous methods, Dorogovtsev, Mendes, and Samukhin [Phys Rev E 64 (2001), 066110] showed that an even more precise result is likely to hold. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005Research supported by NSF Grant ITR 0225610 and DARPA Grant F33615-01-C-1900
Year
DOI
Venue
2005
10.1002/rsa.v26:1/2
Random Struct. Algorithms
Keywords
Field
DocType
phase transition,random graph
Discrete mathematics,Combinatorics,Random graph,Phase transition,struct,Giant component,Percolation,Mathematics
Journal
Volume
Issue
Citations 
26
1-2
5
PageRank 
References 
Authors
0.78
10
3
Name
Order
Citations
PageRank
Béla Bollobás12696474.16
Svante Janson21009149.67
Oliver Riordan350.78