Creating spanning trees in Waiter-Client games
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911816626470912 |
|---|---|
| author | Adamski, Grzegorz Antoniuk, Sylwia Bednarska-Bzdęga, Małgorzata Clemens, Dennis Hamann, Fabian Mogge, Yannick |
| author_facet | Adamski, Grzegorz Antoniuk, Sylwia Bednarska-Bzdęga, Małgorzata Clemens, Dennis Hamann, Fabian Mogge, Yannick |
| contents | For a positive integer $n$ and a tree $T_n$ on $n$ vertices, we consider an unbiased Waiter-Client game $\textrm{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)\le cn$ and $n$ is sufficiently large, then Waiter has a winning strategy in $\textrm{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)\le c'n$ such that Client has a winning strategy in the $\textrm{WC}(n,T_n)$ game for every $n$ sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18534 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Creating spanning trees in Waiter-Client games Adamski, Grzegorz Antoniuk, Sylwia Bednarska-Bzdęga, Małgorzata Clemens, Dennis Hamann, Fabian Mogge, Yannick Combinatorics 05C05, 91A24 For a positive integer $n$ and a tree $T_n$ on $n$ vertices, we consider an unbiased Waiter-Client game $\textrm{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)\le cn$ and $n$ is sufficiently large, then Waiter has a winning strategy in $\textrm{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)\le c'n$ such that Client has a winning strategy in the $\textrm{WC}(n,T_n)$ game for every $n$ sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game. |
| title | Creating spanning trees in Waiter-Client games |
| topic | Combinatorics 05C05, 91A24 |
| url | https://arxiv.org/abs/2403.18534 |