Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 11, 2014, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Dennis Clemens (Freie Universität Berlin)
In the Oriented cycle game, the two players, called OMaker and OBreaker, alternately direct edges of the complete graph on n vertices. OMaker directs exactly one edge, whereas OBreaker is allowed to direct between one and b edges in each round. OMaker wins if the final tournament contains a directed cycle, otherwise OBreaker wins. It is not that difficult see that OMaker has a winning strategy for this game whenever b < n/2 - 2, whereas OBreaker wins for b>n-3. We show that OBreaker has a strategy whenever b > 5n/6. Moreover, we also show that in a variant, where OBreaker is asked to direct exactly b edges in each round, OBreaker wins whenever b>19n/20. Joint work with Anita Liebenau.
Automatic MiSe System Software Version 1.4803M | admin login