Premium
The phase transition in the uniformly grown random graph has infinite order
Author(s) -
Bollobás Béla,
Janson Svante,
Riordan Oliver
Publication year - 2004
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/rsa.20041
Subject(s) - combinatorics , mathematics , vertex (graph theory) , giant component , random graph , discrete mathematics , phase transition , graph , physics , condensed matter physics
The aim of this paper is to study the emergence of the giant component in the uniformly grown random graph G n ( c ), 0 < c < 1, the graph on the set[ 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 G n (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 G n ( c ) is formed by the open bonds in the bond percolation on G n (1) in which a bond is open with probability c . The model G n ( 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 G n ( c ) has order exp(−Θ(1/√ ϵ )) n . In particular, the phase transition in the bond percolation on G n (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., 2005