---- dataentry seminar ----
date_dt : 2011-10-05
title : Coloring random graphs online without creating monochromatic subgraphs
speaker : Dr. Reto Spöhel 
affiliation : Max Planck Institute for Informatics
time : 16h15
room : BC 229
table : seminars
===================
template:datatemplates:seminar
-----------------------


==== abstract ====

Consider the following generalized notion of graph coloring: a coloring of
the vertices of a graph G is \emph{valid} w.r.t. some given graph F if
there is no copy of F in G whose vertices all receive the same color. We
study the problem of computing valid colorings of the binomial random
graph G_{n,p} on n vertices with edge probability p=p(n) in the following
online setting: the vertices of an initially hidden instance of G_{n,p}
are revealed one by one (together with all edges leading to previously
revealed vertices) and have to be colored immediately and irrevocably with
one of r available colors.
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); appeared
at  SODA '11.