login
A217258
Threshold for the P(n)-avoidance edge-coloring game with two colors and fixed tree size restriction, where P(n) denotes the path on n edges (see the comments and reference for precise definition).
0
1, 3, 7, 10, 17, 21, 31, 39, 49, 55, 71, 79, 97
OFFSET
1,2
COMMENTS
The game is played on an edge-colored graph by two players called Builder and Painter. The game starts with a graph on infinitely many vertices with no edges. In each step, Builder adds one new edge to the graph, but he must not create any cycles, and all components (=trees) may have at most k edges (k is fixed throughout the game). Painter immediately and irrevocably colors each new edge red or blue. Painter's goal is to avoid creating a monochromatic (i.e., completely red or completely blue) path P(n) on n edges (n is also fixed throughout the game). Builder's goal is to force Painter to create such a monochromatic P(n). a(n) is defined as the minimal k for which Builder wins this P(n)-avoidance game with two colors and tree size restriction k.
REFERENCES
M. Belfrage, T. Mütze, and R. Spöhel, Probabilistic one-player Ramsey games via deterministic two-player games, SIAM J. Discrete Math., 26(3) (2012), 1031-1049.
FORMULA
a(n) >= n + ceiling(n/2)*(n-1) for all n.
a(n) >= (8/15+o(1))*n^2 as n tends to infinity (the term o(1) tends to 0).
a(n) <= (9+5*sqrt(3))/6*n^(2*log_2(1+sqrt(3))) = Theta(n^2.899...).
EXAMPLE
For n=8, we have a(8)=39, meaning that the P(8)-avoidance game with two colors and tree size restriction k is a win for Builder for all k>=39, and a win for Painter for all k<39.
CROSSREFS
Cf. A221222 (vertex-coloring variant of this game).
Sequence in context: A234638 A345888 A128223 * A258864 A111244 A022120
KEYWORD
nonn,hard,more
AUTHOR
Torsten Muetze, Mar 17 2013
STATUS
approved