Combinatorics Seminar
When: Sunday, November 30, 10am
Where: Schreiber 309
Speaker: Gal Kronenberg, Tel Aviv University
Title: Maker-Breaker games with one random player
Abstract:
Let P be a monotone increasing graph property. The (m:b) Maker-Breaker
game is played on the edge set of K_n, in every round Breaker claims
b edges and then Maker claims m edges. The game ends when all edges
have been claimed. Maker wins if the graph claimed by him satisfies
the property P. Otherwise, Breaker is the winner of the game.
In the (1: b) Maker-Breaker game, a primary question is to find
the maximal value of b such that Maker wins by playing according to
his best strategy (the so called critical bias b^*). Erdos suggested
the following guess which has become known as the probabilistic
intuition. Consider the (1:b) Maker-Breaker game on K_n. Then
the critical bias b^* is the same as the maximal value of b for which
Maker typically wins if both players play randomly. Therefore,
a natural question to ask is how the critical bias changes when
only one player plays randomly.
A random-player Maker-Breaker game is a two-player game, played
the same as an ordinary Maker-Breaker game, except that one player
plays according to his best strategy and claims one element in each
round, while the other plays randomly and claims b elements. In fact,
for every (ordinary) Maker-Breaker game, there are two different
random-player versions: the (1:b) random-Breaker game and
the (b:1) random-Maker game. In this talk, we analyze the random-player
version of several classical Maker-Breaker games such as the Hamilton
cycle game, the perfect matching game and the k-vertex-connectivity
game. For each of these games we find or estimate the asymptotic values
of b that allow each player to typically win the game. We also provide
an explicit winning strategy for the "smart" player for
the corresponding values of b.
Joint work with Michael Krivelevich.