Combinatorics Seminar
When: Sunday, November 28, 10am
Where: Schreiber 309
Speaker: Dan Hefetz, Tel Aviv University
Title: Playing with boxes
Abstract:
In a seminal paper from 1978, Chvatal and Erdos have
introduced biased Maker-Breaker games. In the process of analyzing
such games, they have introduced an auxiliary simple game which
they called "the Box Game". They came up with a simple necessary and
sufficient condition for Maker's win in the Box Game and used it (only
the "sufficient part") to study the biased connectivity game on K_n.
The "necessary part" was never used. This is quite lucky since it is
false. In this talk we fix this mistake (in several ways). If time
permits, I will describe an application of the "necessary part" of
the corrected criterion.
Based on joint works with Michael Krivelevich, Milos Stojakovic and
Tibor Szabo and with Asaf Ferber and Michael Krivelevich.