Waiter-client and client-waiter colourability and \(k\)-SAT games

Wei En Tan¹

¹University of Birmingham

The electronic journal of combinatorics, Tome 24 (2017) no. 2

Résumé

Waiter–Client and Client–Waiter games are two–player, perfect information games, with no chance moves, played on a finite set (board) with special subsets known as the winning sets. Each round of the biased $(1:q)$ Waiter–Client game begins with Waiter offering $q+1$ previously unclaimed elements of the board to Client, who claims one and leaves the remaining $q$ elements to be claimed by Waiter immediately afterwards. In a $(1:q)$ Client–Waiter game, play occurs in the same way except in each round, Waiter offers $t$ elements for any $t$ in the range $1\leqslant t\leqslant q+1$. If Client fully claims a winning set by the time all board elements have been offered, he wins in the Client–Waiter game and loses in the Waiter–Client game. We give an estimate for the threshold bias (i.e. the unique value of $q$ at which the winner of a $(1:q)$ game changes) of the $(1:q)$ Waiter–Client and Client–Waiter versions of two different games: the non–2–colourability game, played on the edge set of a complete $k$–uniform hypergraph, and the $k$–SAT game. More precisely, we show that the threshold bias for the Waiter–Client and Client–Waiter versions of the non–2–colourability game is $\frac{1}{n}\binom{n}{k}2^{\mathcal{O}_k(k)}$ and $\frac{1}{n}\binom{n}{k}2^{-k(1+o_k(1))}$ respectively. Additionally, we show that the threshold bias for the Waiter–Client and Client–Waiter versions of the $k$–SAT game is $\frac{1}{n}\binom{n}{k}$ up to a factor that is exponential and polynomial in $k$ respectively. This shows that these games exhibit the probabilistic intuition.

Détail

DOI : 10.37236/6290

Classification : 05C57, 91A43, 91A05, 91A24, 05C15
Mots-clés : positional games, \(k\)-SAT, colouring