Biased orientation games

DOI10.1016/J.DISC.2012.01.026MaRDI QIDQ418878zbMATH OpenOpenAlexFDO

Authors Ido Ben-Eliezer, Michael Krivelevich, Benny Sudakov

Publication date 30 May 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

directed graphsorientation gameshamiltonicity

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

Cited in

(6)

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

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)