Maker's bounded-degree tree-building conjecture
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.