MEMORYLESS RULES FOR ACHLIOPTAS PROCESSES

In an Achlioptas process two random pairs of {1,...,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 root 5 - 4 + o(1))n = (0.4721 ... + 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 Erdos-Renyi model.