

A217258


Threshold for the P(n)avoidance edgecoloring 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The game is played on an edgecolored 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 oneplayer Ramsey games via deterministic twoplayer games, SIAM J. Discrete Math., 26(3) (2012), 10311049.


LINKS

Table of n, a(n) for n=1..13.
M. Belfrage, T. Mütze, and R. Spöhel, Probabilistic oneplayer Ramsey games via deterministic twoplayer games, arxiv 0911.3810


FORMULA

a(n) >= n + ceiling(n/2)*(n1) 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 (vertexcoloring variant of this game).
Sequence in context: A307191 A234638 A128223 * A258864 A111244 A022120
Adjacent sequences: A217255 A217256 A217257 * A217259 A217260 A217261


KEYWORD

nonn,hard,more


AUTHOR

Torsten Muetze, Mar 17 2013


STATUS

approved



