DC FieldValueLanguage
dc.contributor.authorClemens, Dennis-
dc.contributor.authorLiebenau, Anita-
dc.date.accessioned2020-01-23T12:16:40Z-
dc.date.available2020-01-23T12:16:40Z-
dc.date.issued2016-05-25-
dc.identifier.citationJournal of Combinatorial Theory. Series B (122): 21-54 (2017)de_DE
dc.identifier.issn0095-8956de_DE
dc.identifier.urihttp://hdl.handle.net/11420/4493-
dc.description.abstractIn 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 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 Bollobás and Szabó.en
dc.language.isoende_DE
dc.relation.ispartofJournal of Combinatorial Theory. Series Bde_DE
dc.subjectcyclesde_DE
dc.subjectdigraphsde_DE
dc.subjectorientation gamesde_DE
dc.subject.ddc510: Mathematikde_DE
dc.titleA non-trivial upper bound on the threshold bias of the Oriented-cycle gamede_DE
dc.typeArticlede_DE
dc.type.diniarticle-
dcterms.DCMITypeText-
tuhh.abstract.englishIn 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 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 Bollobás and Szabó.de_DE
tuhh.publisher.doi10.1016/j.jctb.2016.05.002-
tuhh.publication.instituteMathematik E-10de_DE
tuhh.type.opus(wissenschaftlicher) Artikel-
dc.type.driverarticle-
dc.type.casraiJournal Article-
tuhh.container.volume122de_DE
tuhh.container.startpage21de_DE
tuhh.container.endpage54de_DE
dc.identifier.scopus2-s2.0-84969705166-
local.status.inpressfalsede_DE
datacite.resourceTypeJournal Article-
datacite.resourceTypeGeneralText-
item.grantfulltextnone-
item.openairecristypehttp://purl.org/coar/resource_type/c_6501-
item.creatorGNDClemens, Dennis-
item.creatorGNDLiebenau, Anita-
item.openairetypeArticle-
item.fulltextNo Fulltext-
item.cerifentitytypePublications-
item.creatorOrcidClemens, Dennis-
item.creatorOrcidLiebenau, Anita-
item.languageiso639-1en-
item.mappedtypeArticle-
crisitem.author.deptMathematik E-10-
crisitem.author.orcid0000-0001-5940-6556-
crisitem.author.orcid0000-0002-2840-0546-
crisitem.author.parentorgStudiendekanat Elektrotechnik, Informatik und Mathematik-
Appears in Collections:Publications without fulltext

#### Page view(s)

83
Last Week
0
Last month
2
checked on Aug 17, 2022