A non-trivial upper bound on the threshold bias of the Oriented-cycle game

Abstract

In the Oriented-cycle game, introduced by Bollobás and Szabó, two players, called OMaker and OBreaker, alternately direct edges of $K_n$. OMaker directs exactly one edge, whereas OBreaker is allowed to direct between one and $b$ edges. OMaker wins if the final tournament contains a directed cycle, otherwise OBreaker wins. Bollobás and Szabó conjectured that for a bias as large as $n-3$ OMaker has a winning strategy if OBreaker must take exactly $b$ edges in each round. It was shown recently by Ben-Eliezer, Krivelevich and Sudakov, that OMaker has a winning strategy for this game whenever $b\le \frac{n}{2}-2$. In this paper, we show that OBreaker has a winning strategy whenever $b\ge \frac{5n}{6}+2$. Moreover, in case OBreaker is required to direct exactly $b$ edges in each move, we show that OBreaker wins for $b\ge \frac{19n}{20}$, provided that $n$ is large enough. This refutes the conjecture by Bollobás and Szabó.

arXiv comment31 pages, 7 figures