Waiter-client and client-waiter colourability and \(k\)-SAT games (Q2363109): Difference between revisions

Summary: 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 (\textit{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.