|
%I #12 Mar 18 2013 16:55:22
%S 1,3,7,10,17,21,31,39,49,55,71,79,97
%N 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).
%C 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.
%D 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.
%H M. Belfrage, T. Mütze, and R. Spöhel, <a href="http://arxiv.org/abs/0911.3810">Probabilistic one-player Ramsey games via deterministic two-player games</a>, arxiv 0911.3810
%F a(n) >= n + ceiling(n/2)*(n-1) for all n.
%F a(n) >= (8/15+o(1))*n^2 as n tends to infinity (the term o(1) tends to 0).
%F a(n) <= (9+5*sqrt(3))/6*n^(2*log_2(1+sqrt(3))) = Theta(n^2.899...).
%e 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.
%Y Cf. A221222 (vertex-coloring variant of this game).
%K nonn,hard,more
%O 1,2
%A _Torsten Muetze_, Mar 17 2013
|
