Memoryless Rules for Achlioptas Processes
Published in SIAM Journal on Discrete Mathematics, 2009
A. Beveridge, T. Bohman, A. Frieze and O. Pikhurko, Memoryless rules for Achlioptas processes, SIAM Journal on Discrete Mathematics, Vol. 23, Issue 2 (2009), pp. 993–1005.
Preprint link: https://github.com/mathbeveridge/mathbeveridge.github.io/blob/master/files/Memoryless.pdf
In an Achlioptas process two random pairs of $[n]={ 1, \ldots , n }$ arrive in each round and the player has to choose one of them. We study the very restrictive version where player’s decisions cannot depend on the previous history and only one vertex from the two random edges is revealed.