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

作者：Clemens Dennis^*; Liebenau Anita

来源：Journal of Combinatorial Theory - Series B, 2017, 122: 21-54.

DOI：10.1016/j.jctb.2016.05.002

• Orientation games
• Digraphs
• Cycles

In the Oriented-cycle game, introduced by Bollobas and Szabo [7], two players, called OMaker and OBreaker, alternately direct edges of K-n. OMaker directs exactly one previously undirected edge, whereas OBreaker is allowed to direct between one and b previously undirected edges. OMaker wins if the final tournament contains a directed cycle, otherwise OBreaker wins. Bollobas and Szabo [7] 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 [6], that OMaker has a winning strategy for this game whenever b < n/2 - 1. In this paper, we show that OBreaker has a winning strategy whenever b > 5n/6 + 1. Moreover, in case OBreaker is required to direct exactly b edges in each move, we show that OBreaker wins for b >= 19n/20, provided that n is large enough. This refutes the conjecture by Bollobas and Szabo.

• 出版日期2017-1