pith. machine review for the scientific record. sign in

arxiv: 1107.1844 · v1 · submitted 2011-07-10 · 🧮 math.CO

Recognition: unknown

Biased orientation games

Authors on Pith no claims yet
classification 🧮 math.CO
keywords makertournamentwinsgameobtainedbreakergamesgraph
0
0 comments X
read the original 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 $\mathcal P$ 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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.