Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-17T23:26:01.637Z Has data issue: false hasContentIssue false
  • English
  • Français

The Random Graph Intuition for the Tournament Game

Part of: Game theory Graph theory

Published online by Cambridge University Press:  23 September 2015

DENNIS CLEMENS ,
HEIDI GEBAUER  and
ANITA LIEBENAU
DENNIS CLEMENS
Affiliation:
Institut für Mathematik, Technische Universität Hamburg–Harburg, Germany (e-mail: dennis.clemens@tuhh.de)
HEIDI GEBAUER
Affiliation:
Institute of Applied Mathematics and Physics, Zurich University of Applied Sciences, Switzerland (e-mail: geba@zhaw.ch)
ANITA LIEBENAU
Affiliation:
School of Mathematical Sciences, Monash University VIC 3800, Australia (e-mail: anita.liebenau@monash.edu)
Get access Rights & Permissions [Opens in a new window]

Abstract

In 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))log2n, 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))log2n 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))log2n.

MSC classification

Primary: 05C20: Directed graphs (digraphs), tournaments 05C57: Games on graphs
Secondary: 91A24: Positional games (pursuit and evasion, etc.) 91A46: Combinatorial games
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 1: Oberwolfach Special Issue Part 2 , January 2016 , pp. 76 - 88
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Balogh, R., Martin, J. and Pluhár, A. (2009) The diameter game. Random Struct. Alg. 35 369–389.CrossRefGoogle Scholar
[2]Beck, J. (1985) Random graphs and positional games on the complete graph. Ann. Discrete Math. 28 7–13.Google Scholar
[3]Beck, J. (1993) Achievement games and the probabilistic method. In Combinatorics: Paul Erdős is Eighty, Vol. 1, János Bolyai Mathematical Society, pp. 51–78.Google Scholar
[4]Beck, J. (1994) Deterministic graphs games and a probabilistic intuition. Combin. Probab. Comput. 3 13–26.CrossRefGoogle Scholar
[5]Beck, J. (1996) Foundations of positional games. Random Struct. Alg. 9 15–47.3.0.CO;2-E>CrossRefGoogle Scholar
[6]Beck, J. (2008) Combinatorial Games: Tic-Tac-Toe Theory, Vol. 114 of Encyclopedia of Mathematics and its Applications, Cambridge University Press.Google Scholar
[7]Bednarska, M. and Łuczak, T. (2000) Biased positional games for which random strategies are nearly optimal. Combinatorica 20 477–488.CrossRefGoogle Scholar
[8]Bednarska, M. and Łuczak, T. (2001) Biased positional games and the phase transition. Random Struct. Alg. 18 141–152.3.0.CO;2-W>CrossRefGoogle Scholar
[9]Ben-Eliezer, I., Krivelevich, M. and Sudakov, B. (2012) Biased orientation games. Discrete Math. 312 1732–1742.CrossRefGoogle Scholar
[10]Bollobás, B. (2001) Random Graphs, Vol. 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[11]Bollobás, B. and Szabó, T. (1998) The oriented cycle game. Discrete Math. 186 55–67.CrossRefGoogle Scholar
[12]Chartrand, G., Harary, F., Schultz, M. and VanderJagt, D. W. (1995) Achievement and avoidance of a strong orientation of a graph. Congressus Numerantium, pp. 193–204.Google Scholar
[13]Chvátal, V. and Erdős, P. (1978) Biased positional games. Ann. Discrete Math. 2 221–228.CrossRefGoogle Scholar
[14]Clemens, D. and Liebenau, A. (2014) A non-trivial upper bound on the threshold bias of the Oriented-cycle game. arXiv:1404.4529Google Scholar
[15]Erdős, P. and Selfridge, J. (1973) On a combinatorial game. J. Combin. Theory Ser. A 14 298–301.CrossRefGoogle Scholar
[16]Gebauer, H. (2012) On the clique-game. European J. Combin. 33 8–19.CrossRefGoogle Scholar
[17]Gebauer, H. and Szabó, T. (2009) Asymptotic random graph intuition for the biased connectivity game. Random Struct. Alg. 35 431–443.CrossRefGoogle Scholar
[18]Hefetz, D., Krivelevich, M., Stojakovic, M. and Szabó, T. (2008) Planarity, colorability, and minor games. SIAM J. Discrete Math. 22 194–212.CrossRefGoogle Scholar
[19]Stojaković, M. and Szabó, T. (2005) Positional games on random graphs. Random Struct. Alg. 26 204–223.CrossRefGoogle Scholar