Avoidance of a giant component in half the edge set of a random graph

Let e ₁,e ₂,... 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 ⊆ {e ₁,e ₂,..., 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 ₁,..., e _i-1. We describe an on-line algorithm that succeeds whp for m =.9668n. A sequence or events ε _n is said to occur with high probability (whp) if lim _n→ Pr(ε _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* ∈ [.9792,.9793]. We also establish new upper bounds for more restricted Achlioptas processes.