Probabilistic one-player Ramsey games via deterministic two-player games

Michael Belfrage, Torsten Mütze, Reto Spöhel

Consider the following probabilistic one-player game: The board is a graph with $n$ vertices, which initially contains no edges. In each step, a new edge is drawn uniformly at rand…