Waiter–Client and Client–Waiter games
Wei En Tan · University of Birmingham Institutional Research Archive (University of Birmingham) · 2017
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.