login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..13.

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

Cf. A221222 (vertex-coloring 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 23 17:10 EST 2020. Contains 338595 sequences. (Running on oeis4.)