Now showing1 - 2 of 2
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Creating spanning trees in waiter-client games(Australian National University, 2025-08-22); ; ; For a positive integer n and a tree Tn on n vertices, we consider an unbiased Waiter-Client game WC(n, Tn) played on the complete graph Kn, in which Waiterâs goal is to force Client to build a copy of Tn. We prove that for every constant c < 1/3, if â(Tn) †cn and n is sufficiently large, then Waiter has a winning strategy in WC(n, Tn). On the other hand, we show that there exist a positive constant câČ < 1/2 and a family of trees Tn with â(Tn) †câČn such that Client has a winning strategy in the WC(n, Tn) game for every n sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game.Publicationtype: Journal Article11 21 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Tree universality in positional games(Cambridge University Press (CUP), 2025); ; ; 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 <![CDATA[ $K_n$ ]]>, Maker has a strategy to claim a graph which contains copies of all spanning trees with maximum degree at most <![CDATA[ $cn/\log (n)$ ]]>, for a suitable constant <![CDATA[ $c$ ]]> and <![CDATA[ $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.Publicationtype: Journal Article20