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

 

Logo


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 April 7 10:56 EDT 2020. Contains 333301 sequences. (Running on oeis4.)