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.535n is polylogarithmic in n. This resolves a question of Achlioptas. (C) 2001 John Wiley & Sons, Inc.
