DC FieldValueLanguage
dc.contributor.authorClemens, Dennis-
dc.contributor.authorGebauer, Heidi-
dc.contributor.authorLiebenau, Anita-
dc.date.accessioned2020-04-28T18:49:09Z-
dc.date.available2020-04-28T18:49:09Z-
dc.date.issued2016-01-01-
dc.identifier.citationCombinatorics Probability and Computing 1 (25): 76-88 (2016-01-01)de_DE
dc.identifier.issn0963-5483de_DE
dc.identifier.urihttp://hdl.handle.net/11420/5950-
dc.description.abstractIn the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph Kn and selecting one of the two possible orientations. Before the game starts, Breaker fixes an arbitrary tournament Tk on k vertices. Maker wins if, at the end of the game, her digraph contains a copy of Tk; otherwise Breaker wins. In our main result, we show that Maker has a winning strategy for k = (2-o(1))log2 n, improving the constant factor in previous results of Beck and the second author. This is asymptotically tight since it is known that for k = (2-o(1))log2 n Breaker can prevent the underlying graph of Maker's digraph from containing a k-clique. Moreover, the precise value of our lower bound differs from the upper bound only by an additive constant of 12. We also discuss the question of whether the random graph intuition, which suggests that the threshold for k is asymptotically the same for the game played by two 'clever' players and the game played by two 'random' players, is supported by the tournament game. It will turn out that, while a straightforward application of this intuition fails, a more subtle version of it is still valid. Finally, we consider the orientation game version of the tournament game, where Maker wins the game if the final digraph-also containing the edges directed by Breaker-possesses a copy of Tk. We prove that in that game Breaker has a winning strategy for k = (4 + o(1))log2 n.en
dc.language.isoende_DE
dc.relation.ispartofCombinatorics, probability & computingde_DE
dc.titleThe Random Graph Intuition for the Tournament Gamede_DE
dc.typeArticlede_DE
dc.type.diniarticle-
dcterms.DCMITypeText-
tuhh.abstract.englishIn the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph Kn and selecting one of the two possible orientations. Before the game starts, Breaker fixes an arbitrary tournament Tk on k vertices. Maker wins if, at the end of the game, her digraph contains a copy of Tk; otherwise Breaker wins. In our main result, we show that Maker has a winning strategy for k = (2-o(1))log2 n, improving the constant factor in previous results of Beck and the second author. This is asymptotically tight since it is known that for k = (2-o(1))log2 n Breaker can prevent the underlying graph of Maker's digraph from containing a k-clique. Moreover, the precise value of our lower bound differs from the upper bound only by an additive constant of 12. We also discuss the question of whether the random graph intuition, which suggests that the threshold for k is asymptotically the same for the game played by two 'clever' players and the game played by two 'random' players, is supported by the tournament game. It will turn out that, while a straightforward application of this intuition fails, a more subtle version of it is still valid. Finally, we consider the orientation game version of the tournament game, where Maker wins the game if the final digraph-also containing the edges directed by Breaker-possesses a copy of Tk. We prove that in that game Breaker has a winning strategy for k = (4 + o(1))log2 n.de_DE
tuhh.publisher.doi10.1017/S096354831500019X-
tuhh.publication.instituteMathematik E-10de_DE
tuhh.type.opus(wissenschaftlicher) Artikel-
dc.type.driverarticle-
dc.type.casraiJournal Article-
tuhh.container.issue1de_DE
tuhh.container.volume25de_DE
tuhh.container.startpage76de_DE
tuhh.container.endpage88de_DE
dc.identifier.scopus2-s2.0-84952980018-
datacite.resourceTypeJournal Article-
datacite.resourceTypeGeneralText-
item.languageiso639-1en-
item.grantfulltextnone-
item.creatorOrcidClemens, Dennis-
item.creatorOrcidGebauer, Heidi-
item.creatorOrcidLiebenau, Anita-
item.mappedtypeArticle-
item.creatorGNDClemens, Dennis-
item.creatorGNDGebauer, Heidi-
item.creatorGNDLiebenau, Anita-
item.fulltextNo Fulltext-
item.openairetypeArticle-
item.openairecristypehttp://purl.org/coar/resource_type/c_6501-
item.cerifentitytypePublications-
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)

66
Last Week
1
Last month
3
checked on Aug 8, 2022

SCOPUSTM   
Citations

1
Last Week
0
Last month
0
checked on Jun 30, 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.