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.

LINKS

M. Belfrage, T. Mütze, and R. Spöhel, Probabilistic one-player Ramsey games via deterministic two-player games, arxiv 0911.3810

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

KEYWORD

nonn,hard,more

AUTHOR

Torsten Muetze, Mar 17 2013

STATUS

approved