Online Ramsey games for triangles in random graphs

Jzsef Balogh, Jane Butterfield

Research output: Contribution to journalArticlepeer-review

Abstract

In the online F-avoidance edge-coloring game with r colors, a graph on n vertices is generated by randomly adding a new edge at each stage. The player must color each new edge as it appears; the goal is to avoid a monochromatic copy of F. Let N0(F,r,n) be the threshold function for the number of edges that the player is asymptotically almost surely able to paint before he/she loses. Even when F=K3, the order of magnitude of N0(F,r,n) is unknown for r<3. In particular, the only known upper bound is the threshold function for the number of edges in the offline version of the problem, in which an entire random graph on n vertices with m edges is presented to the player to be r edge-colored. We improve the upper bound for the online triangle-avoidance game with r colors, providing the first result that separates the online threshold function from the offline bound for r<3. This supports a conjecture of Marciniszyn, Sphel, and Steger that the known lower bound is tight for cliques and cycles for all r.

Original languageEnglish (US)
Pages (from-to)3653-3657
Number of pages5
JournalDiscrete Mathematics
Volume310
Issue number24
DOIs
StatePublished - Dec 28 2010

Keywords

  • Online Ramsey-games
  • Ramsey number
  • Random graphs
  • Triangle-free

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Online Ramsey games for triangles in random graphs'. Together they form a unique fingerprint.

Cite this