TY - JOUR

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

AU - Clemens, Dennis

AU - Liebenau, Anita

PY - 2017/1

Y1 - 2017/1

N2 - In the Oriented-cycle game, introduced by Bollobás and Szabó [7], two players, called OMaker and OBreaker, alternately direct edges of Kn. 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-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 b5n/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 Bollobás and Szabó.

AB - In the Oriented-cycle game, introduced by Bollobás and Szabó [7], two players, called OMaker and OBreaker, alternately direct edges of Kn. 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-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 b5n/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 Bollobás and Szabó.

KW - Cycles

KW - Digraphs

KW - Orientation games

UR - http://www.scopus.com/inward/record.url?scp=84969705166&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2016.05.002

DO - 10.1016/j.jctb.2016.05.002

M3 - Article

AN - SCOPUS:84969705166

VL - 122

SP - 21

EP - 54

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

SN - 0095-8956

ER -