Addendum to ‘avoiding a giant component’

We take this opportunity, which is kindly provided by the editors, to add a theorem and to correct the proof of one of the lemmas in the article ‘Avoiding a Giant Component’ Bohman and Frieze, Avoiding a giant component, Random Struct Alg 19 (2001), 75–85]. The subject of the said article is the following guided random process. Let e₁, $e^{\prime}_{1}$; e₂, $e^{\prime}_{2}$;…;e_i, $e^{\prime}_{i}$;… be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graph K_n. This sequence is used to form a graph by choosing at stage i, i=1,…, one edge from e_i, $e_{i}^{\prime}$ 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. In Bohman and Frieze Avoiding a giant component, Random Struct Alg 19 (2001), 75–85], we proved that these choices can be made so that whp (A sequence of events ?_n is said to occur with high probability (whp) if lim_n→∞ Pr (?_n)=1.), the size of the largest component of the graph formed at stage. 535n, is polylogarithmic in n. Here, we make a correction to that proof and prove that the graph formed at stage cn for any constant c>1 will contain a component of size Ω(n) (regardless of how the edges are chosen at each stage). © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 126–130, 2002