Online Ramsey games for more than two colors. Issue 3 (7th November 2016)

• Record Type: Journal Article
• Authors: Noever, Andreas
• Is Part Of: Random structures & algorithms. Volume 50:Issue 3(2017)
• Page Start: 464
• Page End: 492
• Publication Date: 2016-11-07
• Subjects: random graphs -- Ramsey games -- thresholds; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20698
• Languages: English
• ISSNs: 1042-9832

Abstract

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