Biased orientation games

DOI10.1016/J.DISC.2012.01.026zbMATH Open1242.05177arXiv1107.1844OpenAlexW2104111637MaRDI QIDQ418878FDOQ418878

Authors: Ido Ben-Eliezer, Michael Krivelevich, Benny Sudakov 

Publication date: 30 May 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We study biased {em orientation games}, in which the board is the complete graph $K_n$, and Maker and Breaker take turns in directing previously undirected edges of $K_n$. At the end of the game, the obtained graph is a tournament. Maker wins if the tournament has some property $mathcalP$ and Breaker wins otherwise. We provide bounds on the bias that is required for a Maker's win and for a Breaker's win in three different games. In the first game Maker wins if the obtained tournament has a cycle. The second game is Hamiltonicity, where Maker wins if the obtained tournament contains a Hamilton cycle. Finally, we consider the $H$-creation game, where Maker wins if the obtained tournament has a copy of some fixed graph $H$.

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

Recommendations

• On the threshold bias in the oriented cycle game
• A non-trivial upper bound on the threshold bias of the oriented-cycle game
• Maker Breaker on digraphs
• Fast strategies in biased Maker-Breaker games
• A remark on the tournament game

zbMATH Keywords

directed graphsorientation gameshamiltonicity

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Graph theory
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Asymptotic random graph intuition for the biased connectivity game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Remarks on positional games. I
• Biased Positional Games
• Combinatorial Games
• On a combinatorial game
• Biased positional games for which random strategies are nearly optimal
• The diameter game
• The oriented cycle game
• Biased positional games and small hypergraphs with large covers
• Tournaments and colouring

Cited In (5)

• The oriented path game
• Maker Breaker on digraphs
• A non-trivial upper bound on the threshold bias of the oriented-cycle game
• Biased Positional Games
• The random graph intuition for the tournament game

This page was built for publication: Biased orientation games

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