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 ISSN 0895-4801.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

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, Engineering and Medicine > 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:	Date Event 2009 Published
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