1 results
Tree universality in positional games
- Part of
-
- Journal:
- Combinatorics, Probability and Computing , First View
- Published online by Cambridge University Press:
- 13 December 2024, pp. 1-21
-
- Article
- Export citation
-
In this paper we consider positional games where the winning sets are edge sets of tree-universal graphs. Specifically, we show that in the unbiased Maker-Breaker game on the edges of the complete graph
$K_n$, Maker has a strategy to claim 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.
