Creating spanning trees in Waiter-Client games

Grzegorz Adamski; Sylwia Antoniuk; Małgorzata Bednarska-Bzdęga; Dennis Clemens; Fabian Hamann; Yannick Mogge

paper

Creating spanning trees in Waiter-Client games

arXiv:2403.18534

Abstract

For a positive integer $n$ and a tree $T_{n}$ on $n$ vertices, we consider an unbiased Waiter-Client game $WC (n, T_{n})$ played on the complete graph~ $K_{n}$ , in which Waiter's goal is to force Client to build a copy of $T_{n}$ . We prove that for every constant $c < 1/3$ , if $Δ (T_{n}) \leq c n$ and $n$ is sufficiently large, then Waiter has a winning strategy in $WC (n, T_{n})$ . On the other hand, we show that there exist a positive constant $c^{'} < 1/2$ and a family of trees $T_{n}$ with $Δ (T_{n}) \leq c^{'} n$ such that Client has a winning strategy in the $WC (n, T_{n})$ game for every $n$ sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game.