Client-waiter games on complete and random graphs (Q504971)

Summary: For a graph \(G\), a monotone increasing graph property \(\mathcal{P}\) and positive integer \(q\), we define the Client-Waiter game to be a two-player game which runs as follows. In each turn Waiter is offering Client a subset of at least one and at most \(q+1\) unclaimed edges of \(G\) from which Client claims one, and the rest are claimed by Waiter. The game ends when all the edges have been claimed. If Client's graph has property \(\mathcal{P}\) by the end of the game, then he wins the game, otherwise Waiter is the winner. In this paper we study several Client-Waiter games on the edge set of the complete graph, and the \(H\)-game on the edge set of the random graph. For the complete graph we consider games where Client tries to build a large star, a long path and a large connected component. We obtain lower and upper bounds on the critical bias for these games and compare them with the corresponding Waiter-Client games and with the probabilistic intuition. For the \(H\)-game on the random graph we show that the known results for the corresponding Maker-Breaker game are essentially the same for the Client-Waiter game, and we extend those results for the biased games and for trees.