Upper Bounds for Online Ramsey Games in Random Graphs

Abstract

Consider the following one-player game. Starting with the empty graph on n vertices, in every step a new edge is drawn uniformly at random and inserted into the current graph. This edge has to be coloured immediately with one of r available colours. The player's goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. We prove an upper bound on the typical duration of this game if F is from a large class of graphs including cliques and cycles of arbitrary size. Together with lower bounds published elsewhere, explicit threshold functions follow.