Abstract 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.

Grzegorz Adamski

Sylwia Antoniuk

Małgorzata Bednarska-Bzdȩga

Dennis Clemens

Fabian Hamann

Yannick Mogge

Combinatorics Probability Computing

双月刊出版的《组合数学、概率与计算》致力于组合数学、概率论和理论计算机科学三个领域。涵盖的主题包括经典和代数图论、极值集理论、拟阵理论、概率方法和随机组合结构；随机组合结构的组合概率和极限定理；算法理论（包括复杂性理论）、随机算法、算法概率分析、计算学习理论和优化。

"Combinatorics Probability and Computing" is a bi-monthly journal dedicated to the fields of combinatorial mathematics, probability theory, and theoretical computer science. The topics covered include classical and algebraic graph theory, extremal set theory, matroid theory, probabilistic methods, and random combinatorial structures; combinatorial probabilities and limit theorems of random combinatorial structures; algorithm theory (including complexity theory), randomized algorithms, probabilistic analysis of algorithms, computational learning theory, and optimization.

《Combinatorics Probability and Computing》是一本双月刊，专注于组合数学、概率论和理论计算机科学三个领域。期刊涵盖的主题包括经典和代数图论、极值集理论、拟阵理论、概率方法和随机组合结构；随机组合结构的组合概率和极限定理；算法理论（包括复杂性理论）、随机算法、算法概率分析、计算学习理论和优化。

Category	Quartile
数学	4
数学, 统计学与概率论	3
数学, 计算机理论方法	4
数学, 数学	4

Tree universality in positional games

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
STATISTICS & PROBABILITY	3