Online Ramsey games for more than two colors |
| |
Authors: | Andreas Noever |
| |
Affiliation: | Department of Computer Science, Institute of Theoretical Computer Science, ETH Zürich, Zürich, Switzerland |
| |
Abstract: | Consider the following one‐player game played on an initially empty graph with n vertices. At each stage a randomly selected new edge is added and the player must immediately color the edge with one of r available colors. Her objective is to color as many edges as possible without creating a monochromatic copy of a fixed graph F. We use container and sparse regularity techniques to prove a tight upper bound on the typical duration of this game with an arbitrary, but fixed, number of colors for a family of 2‐balanced graphs. The bound confirms a conjecture of Marciniszyn, Spöhel and Steger and yields the first tight result for online graph avoidance games with more than two colors. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 464–492, 2017 |
| |
Keywords: | random graphs Ramsey games thresholds |
|
|