The Library
Memoryless rules for achlioptas processes
Tools
Tools
Tools
Beveridge, Andrew, Bohman, Tom, Frieze, Alan and Pikhurko, Oleg (2009) Memoryless rules for achlioptas processes. SIAM Journal on Discrete Mathematics, Vol.23 (No.2). pp. 993-1008. doi:10.1137/070684148
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1137/070684148
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.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science > Mathematics | ||||
| Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||
| ISSN: | 0895-4801 | ||||
| Official Date: | 2009 | ||||
| Dates: |
|
||||
| Volume: | Vol.23 | ||||
| Number: | No.2 | ||||
| Page Range: | pp. 993-1008 | ||||
| DOI: | 10.1137/070684148 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
