Name
Abstract | ||
|---|---|---|
In an Achlioptas process two random pairs of $\{1,\dots,n\}$ arrive in each round and the player has to choose one of them. We study the very restrictive version where a player's decisions cannot depend on the previous history and only one vertex from the two random edges is revealed. We prove that the player can create a giant component in $(2\sqrt{5}-4+o(1))n=(0.4721\ldots+o(1))n$ rounds and that this is the best possible. On the other hand, if the player wants to delay the appearance of a giant, then the optimal bound is $(1/2+o(1))n$, the same as in the Erdős-Rényi model. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/070684148 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
memoryless rules,restrictive version,random pair,previous history,giant component,achlioptas processes,nyi model,random edge,achlioptas process | Discrete mathematics,Combinatorics,Vertex (geometry),Giant component,Mathematics | Journal |
Volume | Issue | ISSN |
23 | 2 | 0895-4801 |
Citations | PageRank | References |
2 | 0.43 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Beveridge | 1 | 55 | 8.21 |
| Tom Bohman | 2 | 250 | 33.01 |
| Alan M. Frieze | 3 | 4837 | 787.00 |
| Oleg Pikhurko | 4 | 318 | 47.03 |