# Differences

This shows you the differences between two versions of the page.

 en:group:seminars:20111005 [2011/09/30 11:12]maatouk en:group:seminars:20111005 [2016/06/23 11:26] Line 1: Line 1: - ---- 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. -