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.publisherAcademic Pressde_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
Show simple item record

Page view(s)

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

Google ScholarTM

Check

Add Files to Item

Note about this record

Cite this record

Export

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