Avoiding a giant component
Tom Bohman, ALAN M. FRIEZE · Random Structures and Algorithms · 2001
Abstract Lete1, e′1;e2, e′2;…;ei, e′i;⋅⋅⋅ be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graphKn(i.e. we sample with replacement). This sequence is used to form a graph by choosing at stagei,i=1,…, one edge fromei,e′ito be an edge in the graph, where the choice at stageiis based only on the observation of the edges that have appeared by stagei. We show that these choices can be made so thatwhpthe size of the largest component of the graph formed at stage 0.535nis polylogarithmic inn. This resolves a question of Achlioptas. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 75–85, 2001