Originator: Martin Erickson (presented by Aisha Arroyo - REGS 2010)
Definitions: Let G be a graph and H be a family of vertex subsets called the winning sets. The Maker-Breaker game on G is a game between two players, Maker and Breaker, who take turns claiming vertices of G. Maker wins by claiming all the vertices in a winning set. Breaker wins if all the vertices have been claimed and Maker does not have a winning set.
Background:
Maker-Breaker games on the edge set of Kn (where players
choosed edges rather than vertices) are well studied. The games with small
winning sets (such as spanning cycles or spanning trees) are overwhelmingly won
by Maker [CE], so two more specific questions have been considered:
1) If we bias the game by letting Breaker claim b edges each time Maker
claims one edge, for how large a b can Maker still win? [CE, BP]
2) For a sufficiently large board (i.e. large n), how many moves does
Maker need to win? [CE, HKSS]
Comments: Bounds for the bias have been found when H is the set of all odd cycles or the set of all even cycles [BP]. Maker needs n+2 moves to claim a Hamiltonian cycle on Kn and n/2+1 moves (for even n) to claim a perfect matching on Kn [HKSS]. The following games are played on n-by-n grid graphs:
Game 1: H is the family of 4-element sets of vertices forming the corners of a square (the square may have any size or location).
Game 2: H is the family of m-element sets of vertices such that no two are in the same row or column.
Question 1: Does Maker win game 1?
Question 2: For what values of m does Maker win game 2?
Question 3: For both of these games, how much bias does Breaker need to win, and how many moves does Maker need to win in the unbiased game?
Comments:
Several of these questions were answered fairly quickly in REGS 2010 by
Kinnersley et al. In the game where Maker seeks the corners of a square (of any
size), Maker wins
in five turns on every n-by-n grid with n≥13. This is sharp
in terms of the number of turns required. In general, if Maker seeks the
points of any "pattern" in any number of dimensions, Gallai's Theorem and a
simple strategy-stealing argument imply that he succeeds when the board is
sufficiently large. It might be worthwhile to consider the biased game, since
then the strategy-stealing argument fails. (Probably Maker still wins
against any constant bias.)
In the game where Maker seeks as large a transversal as possible on
an n-by-n board, Maker can obtain a transversal of size n in
n+1 turns when n≥5 (the results are known and slightly
different for n≤4). The result is best possible in terms of both
transversal size and number of turns needed. Maker can also obtain a
transversal of size n-1 in n-1 turns, but this would hinder his
ability to quickly obtain a transversal of size n.
References:
[CE] V. Chvátal, P. Erdős, Biased positional games, Annals of
Discrete Math. 2 (1978) 221-228.
[HKSS] D. Hefetz, M. Krivelevich, M. Stojaković, T. Szabó, Fast
winning strategies in Maker-Breaker games, Journal of Combinatorial Theory
Ser. B 99 (2009) 39-47.
[BP] Malgorzata Bednarska, Oleg Pikhurko, Odd and even cycles in
Maker-Breaker games, European Journal of Combinatorics 29(3) (2008) 742-745.
~Aisha