Let e(1), e(2),... be a sequence of edges chosen uniformly at random from the edge set of the complete graph K-n (i.e., we sample with replacement). Our goal is to choose, for m as large as possible, a subset E subset of or equal to {e(1),e(2),..., e(2m)}, \E\ = m, such that the size of the largest component in G = ([n], E) is o(n) (i.e., G does not contain a giant component). Furthermore, the selection process must take place on-line; that is, we must choose to accept or reject on e(i) based on the previously seen edges e(1),..., e(i-1). We describe an on-line algorithm that succeeds whp for m = 9668n. A sequence or events F, is said to occur with high probability (whp) if lim(n-->infinity) Pr(E-n) = 1. Furthermore, we find a tight threshold for the off-line version of this question; that is, we find the threshold for the existence of m out of 2m random edges without a giant component. This threshold is m = c*n where c* satisfies a certain transcendental equation, c* is an element of [.9792,.9793]. We also establish new upper bounds for more restricted Achlioptas processes. (C) 2004 Wiley Periodicals, Inc.
