Fast embedding of spanning trees in biased maker-breaker games

MaRDI QIDQ2857367zbMATH OpenFDO

Authors Dan Hefetz, Asaf Ferber, Michael Krivelevich

Publication date 1 November 2013

Full work available at URL https://arxiv.org/abs/1010.2857, http://www.sciencedirect.com/science/article/pii/S1571065311001235

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(4)

• Spanning tree game as prim would have played
• Fast embedding of spanning trees in biased maker-breaker games
• Building spanning trees quickly in 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)