Online Ramsey Games in Random Graphs

Abstract:

Consider the following one-player game: The vertices of a random graph are revealed to the player one by one, along with all edges induced by the vertices revealed so far. The player has to assign one of $r$ available colors to each vertex immediately, without creating a monochromatic copy of some fixed graph $F$. For which values of $p$ can the player asymptotically almost surely (a.a.s.) color the entire random graph $G_{n,p}$? We say that $p_0(n)$ is a threshold for this game if there is a strategy such that the player a.a.s. succeeds if $p\ll p_0$, but a.a.s. fails with any strategy if $p\gg p_0$.

We prove explicit thresholds $p_0(F,r,n)$ for a large family of graphs $F$ including cliques and cycles of arbitrary size, and an arbitrary number $r$ of colors. In particular, we show that the order of magnitude of the threshold depends on the number of colors, in contrast to the corresponding offline problem.

Time permitting, I will also talk about a `balanced' variant of this game, and the edge-coloring analogues of both variants.

(Joint work with Martin Marciniszyn and Angelika Steger.)