The phase transition in the uniformly grown random graph has infinite order

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