TUHH / Institut für Mathematik / Forschungsgebiete / Fast Strategies in Waiter-Client games Englische Flagge

Fast Strategies in Waiter-Client games

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

Collaborators (external): 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(3) (2020), P3.57
[V2021] V. Dvo?ák, Waiter-Client Triangle-Factor Game on the Edges of the Complete Graph, arXiv:2103.00066 (2021)