Tree universality in positional games
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916711018528768 |
|---|---|
| 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 | In this paper we consider positional games where the winning sets are tree universal graphs. Specifically, we show that in the unbiased Maker-Breaker game on the complete graph $K_n$, Maker has a strategy to occupy a graph which contains copies of all spanning trees with maximum degree at most $cn/\log(n)$, for a suitable constant $c$ and $n$ being large enough. We also prove an analogous result for Waiter-Client games. Both of our results show that the building player can play at least as good as suggested by the random graph intuition. Moreover, they improve on a special case of earlier results by Johannsen, Krivelevich, and Samotij as well as Han and Yang for Maker-Breaker games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_00503 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tree universality in positional games Adamski, Grzegorz Antoniuk, Sylwia Bednarska-Bzdęga, Małgorzata Clemens, Dennis Hamann, Fabian Mogge, Yannick Combinatorics 05C05, 91A24 In this paper we consider positional games where the winning sets are tree universal graphs. Specifically, we show that in the unbiased Maker-Breaker game on the complete graph $K_n$, Maker has a strategy to occupy a graph which contains copies of all spanning trees with maximum degree at most $cn/\log(n)$, for a suitable constant $c$ and $n$ being large enough. We also prove an analogous result for Waiter-Client games. Both of our results show that the building player can play at least as good as suggested by the random graph intuition. Moreover, they improve on a special case of earlier results by Johannsen, Krivelevich, and Samotij as well as Han and Yang for Maker-Breaker games. |
| title | Tree universality in positional games |
| topic | Combinatorics 05C05, 91A24 |
| url | https://arxiv.org/abs/2312.00503 |