Combinatorics Seminar
When: Sunday, January 3, 10am
Where: Schreiber 309
Speaker: Dan Hefetz, ETH Zurich
Title: Give Breaker a break (in an unbiased way)
Abstract:
A Maker-Breaker game on a hypergraph (X,F) is a two player
perfect information finite game with no possibility of a draw. The
players take turns in claiming one free element of X (the board
of the game). Maker wins if and only if he is able to fully claim
some element of F. Some Maker-Breaker games are just too easy for
Maker. In order to make things more challenging, Chvatal and Erdos
have suggested to help Breaker by allowing him to claim more board
elements per turn. While this is the most common and highly studied
way of helping Breaker, other natural possibilities exist. In this
talk I will discuss two such possibilities and will exemplify them
by analyzing specific games.
Based on joint works with M. Krivelevich, S. Stojakovic and
T. Szabo and with S. Stich.