Combinatorics Seminar
When: Sunday, January 11, 10am
Where: Schreiber 309
Speaker: Wei En Tan, University of Birmingham
Title: Probabilistic Intuition in Waiter-Client and
Client-Waiter games
Abstract:
For a finite set X, a family F of subsets of X and a positive
integer q, we consider two types of two player, perfect information
games with no chance moves. In each round of the (1 : q) Waiter-Client
game (X, F), the first player, called Waiter, offers the second player,
called Client, q+1 elements of the board X which have not been offered
previously. Client then claims one of these elements and the remaining
q elements go back to Waiter. Waiter wins this game if, by the time
every element of X has been claimed by some player, Client has claimed
all elements of some A in F; otherwise Client is the winner.
Client-Waiter games are defined analogously, the main difference being
that Client wins the game if he manages to claim all elements of some
A in F and Waiter wins otherwise. In this talk, we will look at
the Waiter-Client and Client-Waiter versions of the non-planarity,
Kt-minor and non-k-colourability games. For each such game, we give
a fairly precise estimate of the unique integer q at which the outcome
of the game changes from Client's win to Waiter's win. We also discuss
the relationship between our results, random graphs, and
the corresponding Maker-Breaker games.
This is joint work with Dan Hefetz (University of Birmingham) and
Michael Krivelevich (Tel Aviv University).