Client-waiter games on complete and random graphs

Oren Dean¹ ; Michael Krivelevich

¹Tel-Aviv University

The electronic journal of combinatorics, Tome 23 (2016) no. 4

Résumé

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.

Détail

DOI : 10.37236/6039

Classification : 05C57, 05C80, 91A43, 91A24
Mots-clés : combinatorial games, client-waiter games, random graph