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

详细信息    查看全文

• 作者：Dennis Clemens^a ; ¹ ; ^{dennis.clemens@tuhh.de} ; Anita Liebenau^b ; ² ; ^{anita.liebenau@monash.edu}
• 关键词：Orientation games ; Digraphs ; Cycles
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：21-54
• 全文大小：705 K
• 卷排序：122

文摘

In the Oriented-cycle game, introduced by Bollobás and Szabó [7], two players, called OMaker and OBreaker, alternately direct edges of KnKn. 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. Bollobás and Szabó [7] conjectured that for a bias as large as n−3n−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−1b<n/2−1. In this paper, we show that OBreaker has a winning strategy whenever b>5n/6+1b>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/20b⩾19n/20, provided that n is large enough. This refutes the conjecture by Bollobás and Szabó.