Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 05, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Dan Hefetz
Let P be a monotone decreasing graph property, let G=(V,E) be a graph, and let q be a positive integer. In this talk, I will discuss the (1 : q) Maker-Breaker game, played on the edges of G, in which Maker's goal is to build a graph that does not satisfy the property P. It is clear that in order for Maker to have a chance of winning, G must not satisfy P. It turns out that if G is far from satisfying P, that is, if one has to delete many edges from G in order to obtain a graph that satisfies P, then Maker has a winning strategy for this game. I will also discuss a different notion of being far from satisfying some property, which is motivated by a problem of Duffus, Łuczak and Rödl.
Based on joint work with N. Alon and M. Krivelevich .
Automatic MiSe System Software Version 1.4803M | admin login