Avoiding a giant component

Let e 1 ,  e ′ 1 ; e 2 ,  e ′ 2 ;…; e i ,  e ′ i ;⋅⋅⋅ be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graph K n (i.e. we sample with replacement). This sequence is used to form a graph by choosing at stage i , i =1,…, one edge from e i , e ′ i to be an edge in the graph, where the choice at stage i is based only on the observation of the edges that have appeared by stage i . We show that these choices can be made so that whp the size of the largest component of the graph formed at stage 0.535 n is polylogarithmic in n . This resolves a question of Achlioptas. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 75–85, 2001