Maker's bounded-degree tree-building conjecture

Let KnK_n be the complete graph on nn vertices, and let Tn{\mathcal T}_n denote the family of spanning trees on these vertices. In the Maker–Breaker game (E(Kn),Tn)(E(K_n),{\mathcal T}_n), Maker claims edges while Breaker claims the remaining edges; write Δ(T)\Delta(T) for the maximum degree of a tree TT. Maker's bounded-degree tree-building conjecture. For every positive integer Δ\Delta, there exists an integer n0=n0(Δ)n_0=n_0(\Delta) such that, for every nn0n\geq n_0 and every tree T=(V,E)T=(V,E) with V=n|V|=n and Δ(T)Δ\Delta(T)\leq\Delta, Maker has a strategy to win the game (E(Kn),Tn)(E(K_n),{\mathcal T}_n) within nn moves. The conjecture asserts that every sufficiently large bounded-degree tree can be built with at most one wasted move beyond the theoretical minimum of n1n-1 moves; the paper establishes this bound for trees with a long bare path and an n+1n+1-move bound in general, leaving the stated uniform nn-move bound open.

Sources & referencesView supporting material

Primary source

Dennis Clemens, Asaf Ferber, Roman Glebov, Dan Hefetz and Anita Liebenau, “Building spanning trees quickly in Maker-Breaker games”, arXiv:1304.4108 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.