## Abstract

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 ⊆ {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 ε _{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.

Original language | English |
---|---|

Pages (from-to) | 432-449 |

Number of pages | 18 |

Journal | Random Structures and Algorithms |

Volume | 25 |

Issue number | 4 |

DOIs | |

Publication status | Published - Dec 2004 |

Externally published | Yes |