When: Sunday, March 10, 10am
Where: Schreiber 309
Speaker: Anita Liebenau, Berlin
Title: Orientation Games
In an orientation game, two players called OMaker and OBreaker take turns in directing previously undirected edges of the complete graph on n vertices. The final graph is a tournament. OMaker wins if this tournament has some predefined property P, otherwise OBreaker wins. We analyse the Oriented-cycle game, in which OMakers goal is to close a directed cycle. Since this game is drastically in favour of OMaker, we allow OBreaker to direct (up to) b>1 edges in each of his moves and ask for the largest b* such that OMaker has a winning strategy (the so called threshold bias). It is known that n/2-3 < b* < n-2, where the upper bound was conjectured to be tight. In this talk I will discuss recent developments in the field of orientation games, including a sketch of an OBreaker strategy which improves the upper bound on b* to roughly 5n/6.
Joint work with Dennis Clemens.
