The Online Clique Avoidance Game on Random Graphs

摘要

Consider the following one player game on an empty graph with n vertices. The edges are presented one by one to the player in a random order. One of two colors, red or blue, has to be assigned to each edge immediately. The player's object is to color as many edges as possible without creating a monochromatic clique K_l of some fixed size l. We prove a threshold phenomenon for the expected duration of this game. We show that there is a function N_0 = N_0(l, n) such that the player can asymptotically almost surely survive up to N(n) N_0 edges by playing greedily and that this is best possible, i.e., there is no strategy such that the game would last for N(n) N_0 edges.