go-v.orgdoi

Balanced Online Ramsey Games in Random Graphs

Anupam Prakash, Reto Spöhel, Henning Thomas · The Electronic Journal of Combinatorics · 2009

  • DOI 10.37236/100
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2009

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2009

Abstract

Consider the following one-player game. Starting with the empty graph on $n$ vertices, in every step $r$ new edges are drawn uniformly at random and inserted into the current graph. These edges have to be colored immediately with $r$ available colors, subject to the restriction that each color is used for exactly one of these edges. The player's goal is to avoid creating a monochromatic copy of some fixed graph $F$ for as long as possible. We prove explicit threshold functions for the duration of this game for an arbitrary number of colors $r$ and a large class of graphs $F$. This extends earlier work for the case $r=2$ by Marciniszyn, Mitsche, and Stojaković.

We also prove a similar threshold result for the vertex-coloring analogue of this game.

Open the resolved locator · 10.37236/100

Metadata licence: OpenAlex metadata (CC0)