Znanstveni kolokviji

On-line Ramsey theory

Vrijeme: 19.12.2007
Predavaonica: 005
Predavač: Prof. Goran Konjevod, Department of Computer Science and Engineering, School of Computing and Informatics, Ira A. Fulton School of Engineering, Arizona State University, USA
Naziv: On-line Ramsey theory

Two players, Builder and Painter, play the following game on a fixed set of vertices V. In one round Builder presents an edge e linking two previously independent vertices of V and Painter paints e using one of c colors. Builder's goal is to force Painter to create a monochromatic copy of a fixed graph F. If there are no other restrictions then Painter has no chances to avoid F (by Ramsey's theorem). But what if Builder is not allowed to construct a graph whose chromatic number exceeds that of F? We prove that even with this obstacle Builder wins this game for any number of colors. Our main tool is an auxiliary ''Ramsey survival game'', which is interesting in its own right.

<< Povratak na popis kolokvija

Copyright (c) 2004-2007, Vedran Šego