Verlagslink DOI: 10.1016/j.jctb.2016.05.002
Titel: A non-trivial upper bound on the threshold bias of the Oriented-cycle game
Sprache: Englisch
Autor/Autorin: Clemens, Dennis  
Liebenau, Anita 
Schlagwörter: cycles; digraphs; orientation games
Erscheinungs­datum: 25-Mai-2016
Verlag: Academic Press
Quellenangabe: Journal of Combinatorial Theory. Series B (122): 21-54 (2017)
Zusammenfassung (englisch): 
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ó.
URI: http://hdl.handle.net/11420/4493
ISSN: 0095-8956
Zeitschrift: Journal of Combinatorial Theory. Series B 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

88
Letzte Woche
0
Letzten Monat
2
checked on 06.10.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.