Name
Abstract | ||
|---|---|---|
The classical result in the theory of random graphs, proved by Erdős and Rényi in 1960, concerns the threshold for the appearance of the giant component in the random graph process. We consider a variant of this problem, with a Ramsey flavor. Now, each random edge that arrives in a sequence of rounds must be colored with one of r colors. The goal can be either to create a giant component in every color class, or alternatively, to avoid it in every color. One can analyze the offline or online setting for this problem. In this paper, we consider all these variants and provide nontrivial upper and lower bounds; in certain cases (like online avoidance) the obtained bounds are asymptotically tight. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011 © 2011 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1002/rsa.20343 | Random Struct. Algorithms |
Keywords | Field | DocType |
online setting,random graph,wiley periodicals,ramsey game,giant component,inc. random struct,random graph process,random edge,online avoidance,color class,r color,random graphs,upper and lower bounds | Discrete mathematics,Random regular graph,Colored,Combinatorics,Random graph,Upper and lower bounds,struct,Giant component,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 1-2 | 1042-9832 |
Citations | PageRank | References |
3 | 0.42 | 17 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| michael krivelevich | 3 | 1688 | 179.90 |
| Po-Shen Loh | 4 | 133 | 18.68 |
| Benny Sudakov | 5 | 1391 | 159.71 |