Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
https://doi.org/10.21256/zhaw-15843| Publikationstyp: | Beitrag in wissenschaftlicher Zeitschrift |
| Art der Begutachtung: | Peer review (Publikation) |
| Titel: | The random graph intuition for the tournament game |
| Autor/-in: | Clemens, Dennis Gebauer, Heidi Liebenau, Anita |
| DOI: | 10.1017/S096354831500019X 10.21256/zhaw-15843 |
| Erschienen in: | Combinatorics, Probability and Computing |
| Band(Heft): | 25 |
| Heft: | 1 |
| Seite(n): | 76 |
| Seiten bis: | 88 |
| Erscheinungsdatum: | 2015 |
| Verlag / Hrsg. Institution: | Cambridge University Press |
| ISSN: | 0963-5483 1469-2163 |
| Sprache: | Englisch |
| Schlagwörter: | Mathematics - combinatorics |
| Fachgebiet (DDC): | 510: Mathematik |
| Zusammenfassung: | In the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph on n vertices and selecting one of the two possible orientations. Before the game starts, Breaker fixes an arbitrary tournament T_k on k vertices. Maker wins if, at the end of the game, her digraph contains a copy of T_k; otherwise Breaker wins. In our main result, we show that Maker has a winning strategy for k = (2-o(1))log_2 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))log_2 n Breaker can prevent that the underlying graph of Maker's graph contains 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 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 – containing also the edges directed by Breaker – possesses a copy of T_k. We prove that in that game Breaker has a winning strategy for k = (4+o(1))log_2 n. |
| Weitere Angaben: | Erworben im Rahmen der Schweizer Nationallizenzen (http://www.nationallizenzen.ch) |
| URI: | https://digitalcollection.zhaw.ch/handle/11475/15843 |
| Volltext Version: | Publizierte Version |
| Lizenz (gemäss Verlagsvertrag): | Lizenz gemäss Verlagsvertrag |
| Departement: | School of Engineering |
| Organisationseinheit: | Institut für Angewandte Mathematik und Physik (IAMP) |
| Enthalten in den Sammlungen: | Publikationen School of Engineering |
Dateien zu dieser Ressource:
| Datei | Beschreibung | Größe | Format | |
|---|---|---|---|---|
| 2015_Clemens-etal_Random-graph-intuition-for-the-tournament-game.pdf | 166.6 kB | Adobe PDF |  Öffnen/Anzeigen |
Zur Langanzeige
Clemens, D., Gebauer, H., & Liebenau, A. (2015). The random graph intuition for the tournament game. Combinatorics, Probability and Computing, 25(1), 76–88. https://doi.org/10.1017/S096354831500019X
Clemens, D., Gebauer, H. and Liebenau, A. (2015) ‘The random graph intuition for the tournament game’, Combinatorics, Probability and Computing, 25(1), pp. 76–88. Available at: https://doi.org/10.1017/S096354831500019X.
D. Clemens, H. Gebauer, and A. Liebenau, “The random graph intuition for the tournament game,” Combinatorics, Probability and Computing, vol. 25, no. 1, pp. 76–88, 2015, doi: 10.1017/S096354831500019X.
CLEMENS, Dennis, Heidi GEBAUER und Anita LIEBENAU, 2015. The random graph intuition for the tournament game. Combinatorics, Probability and Computing. 2015. Bd. 25, Nr. 1, S. 76–88. DOI 10.1017/S096354831500019X
Clemens, Dennis, Heidi Gebauer, and Anita Liebenau. 2015. “The Random Graph Intuition for the Tournament Game.” Combinatorics, Probability and Computing 25 (1): 76–88. https://doi.org/10.1017/S096354831500019X.
Clemens, Dennis, et al. “The Random Graph Intuition for the Tournament Game.” Combinatorics, Probability and Computing, vol. 25, no. 1, 2015, pp. 76–88, https://doi.org/10.1017/S096354831500019X.
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.