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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
en:group:seminars:20111005 [2011/09/15 13:28]
en:group:seminars:20111005 [2011/09/30 11:12]
Line 1: Line 1:
 ---- dataentry seminar ---- ---- dataentry seminar ----
 date_dt : 2011-10-05 date_dt : 2011-10-05
-title : TBA+title : Coloring random graphs online without creating monochromatic subgraphs
 speaker : Dr. Reto Spöhel ​ speaker : Dr. Reto Spöhel ​
 affiliation : Max Planck Institute for Informatics affiliation : Max Planck Institute for Informatics
Line 13: Line 13:
 ==== abstract ==== ==== 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.