Combinatorics Seminar

When: Sunday, November 30, 10am
Where: Schreiber 309
Speaker: Gal Kronenberg, Tel Aviv University
Title: Maker-Breaker games with one random player


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.