Fast Strategies in Waiter-Client games

Collaborators (MAT): Dr. Dennis Clemens, Fabian Hamann, M. Sc., Yannick Mogge, M. Sc.

Collaborators (external): Pranshu Gupta, Alexander Haupt, Mirjana Mikalački

Biased Waiter-Client games (formerly known as Picker-Chooser games, see e.g. [a]) are a variant of Maker-Breaker games, in which during each round Waiter offers to Client \(b+1\) unclaimed elements of which Client claims one element, while the rest go to Waiter. If by the end of the game Waiter could force Client to occupy all elements of some winning set, she wins the game, otherwise Client wins.

One option now is to consider fast strategies. Here the question is not only if Waiter can win a specific game, but also how fast she can win. If the size of a the smallest winning set coincides with the number of turns, in which Waiter is able to win, we say that the game is won perfectly fast, if she only requires a constant number of additional turns, we say the game is won asymptotically fast.

References

[CGHHMM2020] D. Clemens, P. Gupta, F. Hamann, A. Haupt, M. Mikalački, and Y. Mogge. Fast Strategies in Waiter-Client Games, The Electronic Journal of Combinatorics 27 (2020), no. 3, P3.57.
[V2021] V. Dvořák, Waiter-Client Triangle-Factor Game on the Edges of the Complete Graph, European Journal of Combinatorics 96 (2021), 103356.