Fast embedding of spanning trees in biased maker-breaker games

zbMATH Open1274.05320arXiv1010.2857MaRDI QIDQ2857367FDOQ2857367

Authors: Dan Hefetz, Asaf Ferber, Michael Krivelevich 

Publication date: 1 November 2013

Abstract: Given a tree $T=(V,E)$ on $n$ vertices, we consider the $(1:q)$ Maker-Breaker tree embedding game ${mathcalT}_n$. The board of this game is the edge set of the complete graph on $n$ vertices. Maker wins ${mathcalT}_n$ if and only if he is able to claim all edges of a copy of $T$. We prove that there exist real numbers $alpha,epsilon>0$ such that, for sufficiently large $n$ and for every tree $T$ on $n$ vertices with maximum degree at most $n^{epsilon}$, Maker has a winning strategy for the $(1:q)$ game ${mathcalT}_n$, for every $qleq{n}^{alpha}$. Moreover, we prove that Maker can win this game within $n+o(n)$ moves which is clearly asymptotically optimal.

Full work available at URL: https://arxiv.org/abs/1010.2857

Recommendations

• Fast embedding of spanning trees in biased maker-breaker games
• Building spanning trees quickly in maker-breaker games
• Building spanning trees quickly in maker-breaker games
• Asymptotic random graph intuition for the biased connectivity game
• On Biased Positional Games

Mathematics Subject Classification ID

Trees (05C05) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Asymptotic random graph intuition for the biased connectivity game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Fast winning strategies in maker-breaker games
• Deterministic Graph Games and a Probabilistic Intuition
• Hamilton cycles in highly connected and expanding graphs
• On Biased Positional Games

Cited In (4)

• Spanning tree game as prim would have played
• Building spanning trees quickly in maker-breaker games
• Fast embedding of spanning trees in biased maker-breaker games
• Winning fast in biased maker-breaker games

This page was built for publication: Fast embedding of spanning trees in biased maker-breaker games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2857367)