Publisher DOI: 10.1016/j.jctb.2016.05.002
Title: A non-trivial upper bound on the threshold bias of the Oriented-cycle game
Language: English
Authors: Clemens, Dennis  
Liebenau, Anita 
Keywords: cycles; digraphs; orientation games
Issue Date: 25-May-2016
Publisher: Academic Press
Source: Journal of Combinatorial Theory. Series B (122): 21-54 (2017)
Abstract (english): 
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ó.
ISSN: 0095-8956
Journal: Journal of Combinatorial Theory. Series B 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 5, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.