Name
Abstract | ||
|---|---|---|
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 e1, 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 graph Kn. This sequence is used to form a graph by choosing at stage i, i = 1,..., one edge from ei, e'i 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 en is said to occur with high probability (whp) if limn → ∞ Pr(en) = 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). |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1002/rsa.10018 | Random Struct. Algorithms |
Keywords | Field | DocType |
constant c,complete graph,random process,largest component,random struct alg,stage i,high probability,stage cn,giant component | Discrete mathematics,Complete graph,Combinatorics,struct,Stochastic process,Ordered pair,Giant component,Mathematics,Lemma (mathematics),Addendum,Frieze | Journal |
Volume | Issue | Citations |
20 | 1 | 1 |
PageRank | References | Authors |
0.82 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Alan M. Frieze | 2 | 4837 | 787.00 |