Biased orientation games

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

Benny Sudakov, Ido Ben-Eliezer, Michael Krivelevich

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

zbMATH Keywords

directed graphsorientation gameshamiltonicity

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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 (4)

• Maker Breaker on digraphs
• A non-trivial upper bound on the threshold bias of the oriented-cycle game
• The Random Graph Intuition for the Tournament Game
• Biased Positional Games

   Recommendations

• A non-trivial upper bound on the threshold bias of 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 👍 👎

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)