Search

We initiate the study of a new variant of the Maker-Breaker positional game, which we call multistage game. Given a hypergraph H = (X , F) and a bias b ≥ 1 , the (1 : b) multistage Maker-Breaker game on H is played in several stages as follows. Each stage is played as a usual (1 : b) Maker-Breaker game, until all the elements of the board get claimed by one of the players, with the first stage being played on H. In every subsequent stage, the game is played on the board reduced to the elements that Maker claimed in the previous stage, and with the winning sets reduced to those fully contained in the new board. The game proceeds until no winning sets remain, and the goal of Maker is to prolong the duration of the game for as many stages as possible. In this paper we estimate the maximum duration of the (1 : b) multistage Maker-Breaker game, for biases b subpolynomial in n , for some standard graph games played on the edge set of K n : the connectivity game, the Hamilton cycle game, the non- k -colorability game, the pancyclicity game and the H -game. While the first three games exhibit a probabilistic intuition, it turns out that the last two games fail to do so. [ABSTRACT FROM AUTHOR]

We study ( a : a ) Maker–Breaker games played on the edge set of the complete graph on n vertices. In the following four games — perfect matching game, Hamilton cycle game, star factor game and path factor game, our goal is to determine the least number of moves which Maker needs in order to win these games. Moreover, for all games except for the star factor game, we show how first player can win in the strong version of these games. [ABSTRACT FROM AUTHOR]

We study the ( a : a ) Maker-Breaker games played on the edge set of the complete graph on n vertices. In the following four games – perfect matching game, Hamiltonicity game, star factor game and path factor game, our goal is to determine the least number of moves which Maker needs in order to win these games. Moreover, for all games except for the star factor game, we show how Red can win in the strong version of these games. [ABSTRACT FROM AUTHOR]

For a tree T on n vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on n vertices, which Maker wins as soon as the graph she builds contains a copy of T. We prove that if T has bounded maximum degree and n is sufficiently large, then Maker can win this game within n + 1 moves. Moreover, we prove that Maker can build almost every tree on n vertices in n-1 moves and provide nontrivial examples of families of trees which Maker cannot build in n - 1 moves. [ABSTRACT FROM AUTHOR]