Coloring random graphs online without creating monochromatic subgraphs

It is known that for any fixed graph F and any fixed integer r\geq 2 this problem has a threshold p_0(F,r,n) in the following sense: For any function p(n) = o(p_0) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of G_{n,p} that is valid w.r.t. F online, and for any function p(n)=\omega(p_0) \emph{any} online strategy will a.a.s. fail to do so.

We establish a general correspondence between this probabilistic problem and a deterministic two-player game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a value \gamma=\gamma(F,r) such that the threshold of the probabilistic problem is given by p_0(F,r,n)=n^{-\gamma}. Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of G_{n,p} online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n^{-\gamma}).

Joint work with Torsten Mütze und Thomas Rast (both ETH Zurich); to appear in Proceedings of SODA '11.