Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 29, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Henning Thomas
We consider the following one-player game: The player, called Painter, starts with the empty graph on n vertices. In every step she is presented r edges drawn u.a.r. from all remaining ones, which she has to color instantly with r available colors using each color exactly once. Her goal is to avoid a monochromatic copy of a given fixed graph F as long as possible. Marciniszyn, Mitsche and Stojakovic proved a threshold phenomenon for the duration of this game for r=2 and a variety of graphs F, e.g. cycles. Using different techniques (the methods of first and second moment) we extend their result to an arbitrary number of colors and a larger class of graphs, e.g. cliques of size t if r \geq t. We also discuss ideas on a general threshold for arbitrary graphs.
Automatic MiSe System Software Version 1.4803M | admin login