2010/10/14 by Asaf Ferber, Ferber, Asaf, Dan Hefetz +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1010.2857
20 pages
arxiv created 2010/10/14 · arxiv updated 2010/10/15
Given a tree T=(V,E) on n vertices, we consider the (1 : q) Maker-Breaker tree embedding game \mathcal Tn. The board of this game is the edge set of the complete graph on n vertices. Maker wins \mathcal Tn if and only if he is able to claim all edges of a copy of T. We prove that there exist real numbers α, ε> 0 such that, for sufficiently large n and for every tree T on n vertices with maximum degree at most nε, Maker has a winning strategy for the (1 : q) game \mathcal Tn, for every q ≤ nα. Moreover, we prove that Maker can win this game within n + o(n) moves which is clearly asymptotically optimal.