Combinatorics Seminar
When: Sunday, January 29, 10am
Where: Schreiber 309
Speaker: Asaf Ferber, Tel Aviv University
Title: Winning fast in Maker-Breaker games played on
sparse random boards
Abstract:
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.