{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T11:55:43Z","timestamp":1694260543951},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2015,9,23]],"date-time":"2015-09-23T00:00:00Z","timestamp":1442966400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>In the <jats:italic>tournament game<\/jats:italic> two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph <jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic> and selecting one of the two possible orientations. Before the game starts, Breaker fixes an arbitrary tournament <jats:italic>T<jats:sub>k<\/jats:sub><\/jats:italic> on <jats:italic>k<\/jats:italic> vertices. Maker wins if, at the end of the game, her digraph contains a copy of <jats:italic>T<jats:sub>k<\/jats:sub><\/jats:italic>; otherwise Breaker wins. In our main result, we show that Maker has a winning strategy for <jats:italic>k<\/jats:italic> = (2 \u2212 <jats:italic>o<\/jats:italic>(1))log<jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic>, improving the constant factor in previous results of Beck and the second author. This is asymptotically tight since it is known that for <jats:italic>k<\/jats:italic> = (2 \u2212 <jats:italic>o<\/jats:italic>(1))log<jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic> Breaker can prevent the underlying graph of Maker's digraph from containing a <jats:italic>k<\/jats:italic>-clique. Moreover, the precise value of our lower bound differs from the upper bound only by an <jats:italic>additive constant<\/jats:italic> of 12.<\/jats:p><jats:p>We also discuss the question of whether the random graph intuition, which suggests that the threshold for <jats:italic>k<\/jats:italic> is asymptotically the same for the game played by two \u2018clever\u2019 players and the game played by two \u2018random\u2019 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.<\/jats:p><jats:p>Finally, we consider the <jats:italic>orientation game<\/jats:italic> version of the tournament game, where Maker wins the game if the final digraph \u2013 also containing the edges directed by Breaker \u2013 possesses a copy of <jats:italic>T<jats:sub>k<\/jats:sub><\/jats:italic>. We prove that in that game Breaker has a winning strategy for <jats:italic>k<\/jats:italic> = (4 + <jats:italic>o<\/jats:italic>(1))log<jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s096354831500019x","type":"journal-article","created":{"date-parts":[[2015,9,23]],"date-time":"2015-09-23T01:33:07Z","timestamp":1442971987000},"page":"76-88","source":"Crossref","is-referenced-by-count":2,"title":["The Random Graph Intuition for the Tournament Game"],"prefix":"10.1017","volume":"25","author":[{"given":"DENNIS","family":"CLEMENS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HEIDI","family":"GEBAUER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANITA","family":"LIEBENAU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2015,9,23]]},"reference":[{"key":"S096354831500019X_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20279"},{"key":"S096354831500019X_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.07.005"},{"key":"S096354831500019X_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/060654414"},{"key":"S096354831500019X_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(73)90005-8"},{"key":"S096354831500019X_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70335-2"},{"key":"S096354831500019X_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<15::AID-RSA2>3.0.CO;2-E"},{"key":"S096354831500019X_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000936"},{"key":"S096354831500019X_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.01.026"},{"key":"S096354831500019X_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20280"},{"key":"S096354831500019X_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20059"},{"key":"S096354831500019X_ref12","first-page":"193","article-title":"Achievement and avoidance of a strong orientation of a graph","author":"Chartrand","year":"1995","journal-title":"Congressus Numerantium"},{"key":"S096354831500019X_ref6","volume-title":"Encyclopedia of Mathematics and its Applications","author":"Beck","year":"2008"},{"key":"S096354831500019X_ref10","volume-title":"Cambridge Studies in Advanced Mathematics","author":"Bollob\u00e1s","year":"2001"},{"key":"S096354831500019X_ref2","first-page":"7","article-title":"Random graphs and positional games on the complete graph.","volume":"28","author":"Beck","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"S096354831500019X_ref3","unstructured":"Beck J. (1993) Achievement games and the probabilistic method. In Combinatorics: Paul Erd\u0151s is Eighty, Vol. 1, J\u00e1nos Bolyai Mathematical Society, pp. 51\u201378."},{"key":"S096354831500019X_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00224-0"},{"key":"S096354831500019X_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200103)18:2<141::AID-RSA1002>3.0.CO;2-W"},{"key":"S096354831500019X_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070002"},{"key":"S096354831500019X_ref14","unstructured":"Clemens D. and Liebenau A. (2014) A non-trivial upper bound on the threshold bias of the Oriented-cycle game. arXiv:1404.4529"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831500019X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T19:41:33Z","timestamp":1555702893000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831500019X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,23]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["S096354831500019X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831500019x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,23]]}}}