Maker's bounded-degree tree-building conjecture
Maker's bounded-degree tree-building conjecture
Let be the complete graph on vertices, and let denote the family of spanning trees on these vertices. In the Maker–Breaker game , Maker claims edges while Breaker claims the remaining edges; write for the maximum degree of a tree . Maker's bounded-degree tree-building conjecture. For every positive integer , there exists an integer such that, for every and every tree with and , Maker has a strategy to win the game within 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 moves; the paper establishes this bound for trees with a long bare path and an -move bound in general, leaving the stated uniform -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.