Waiter–Client and Client–Waiter games

Tan, Wei En (2017). Waiter–Client and Client–Waiter games. University of Birmingham. Ph.D.

Preview

Tan17PhD.pdf
PDF - Accepted Version
Download (883kB)

Abstract

In this thesis, we consider two types of positional games; $Waiter$ - $Client$ and $Client$ - $Waiter$ games. Each round in a biased ( $a$ : $b$ ) game begins with Waiter offering a+b free elements of the board to Client. Client claims $a$ elements among these and the remaining $b$ elements are claimed by Waiter. Waiter wins in a Waiter-Client game if he can force Client to fully claim a $winning$ $set$ , otherwise Client wins. In a Client-Waiter game, Client wins if he can claim a winning set himself, else Waiter wins.

We estimate the $threshold$ $bias$ of four different ( $1$ : $q$ ) Waiter-Client and Client-Waiter games. This is the unique value of Waiter's bias $q$ at which the player with a winning strategy changes. We find its asymptotic value for both versions of the complete-minor and non-planarity games and give bounds for both versions of the non- $r$ -colourability and $k$ -SAT games. Our results show that these games exhibit a heuristic called the $probabilistic$ $intuition$ .

We also find sharp probability thresholds for the appearance of a graph in the random graph $G$ ( $n$ , $p$ ) on which Waiter and Client win the ( $1$ : $q$ ) Waiter-Client and Client-Waiter Hamiltonicity games respectively.