The ACO Seminar (2011-2012)

In this talk we consider Maker-Breaker games played on random boards. Given a graph G=(V,E) and a graph property P, the Maker-Breaker game P played on G is defined as follows. In every round Maker and Breaker alternately claim free edges from E. Maker wins this game as soon as his graph possesses P. Otherwise, Breaker wins the game.

We consider the perfect matching, hamiltonicity and k-connectivity games played on a sparse random board G(n,p), p>=polylog(n)/n. It is clear that Maker needs at least n/2, n, kn/2 moves to win these games, respectively. We prove that G(n,p) is typically such that Maker has a strategy to win within n/2+o(n), n+o(n), kn/2+o(n) moves, respectively. We also show a connection between fast strategies in Maker-Breaker games (weak games) and Maker-Maker games (strong games).

Joint work with Dennis Clemens, Anita Liebenau and Michael Krivelevich.