The random graph intuition for the tournament game

DOI10.1017/S096354831500019XMaRDI QIDQ5364264zbMATH OpenFDO

Authors Dennis Clemens, Heidi Gebauer, Anita Liebenau

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.4229

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Games on graphs (graph-theoretic aspects) (05C57) Positional games (pursuit and evasion, etc.) (91A24) Combinatorial games (91A46)

Abstract: 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.

Recommendations

• A remark on the tournament game
• On the clique-game
• On the threshold bias in the oriented cycle game
• Biased orientation games
• A threshold for the maker-breaker clique game

Cites work

• scientific article; zbMATH DE number 3970795 (Why is no real title available?)
• scientific article; zbMATH DE number 1185329 (Why is no real title available?)
• scientific article; zbMATH DE number 524119 (Why is no real title available?)
• scientific article; zbMATH DE number 932175 (Why is no real title available?)
• A non-trivial upper bound on the threshold bias of the oriented-cycle game
• Asymptotic random graph intuition for the biased connectivity game
• Biased Positional Games
• Biased orientation games
• Biased positional games and the phase transition
• Biased positional games for which random strategies are nearly optimal
• Combinatorial Games
• Deterministic Graph Games and a Probabilistic Intuition
• On a combinatorial game
• On the clique-game
• Planarity, Colorability, and Minor Games
• Positional games on random graphs
• Random graphs.
• The diameter game
• The oriented cycle game

Cited in

(6)

• On the clique-game
• A non-trivial upper bound on the threshold bias of the oriented-cycle game
• A remark on the tournament game
• Determining the results of tournament games using complete graphs generation
• Multistage positional games
• Tournament games and positive tournaments

This page was built for publication: The random graph intuition for the tournament game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364264)