TY - JOUR

T1 - Online Ramsey games for triangles in random graphs

AU - Balogh, Jzsef

AU - Butterfield, Jane

N1 - Funding Information:
We are indebted to John Lenz and Wojciech Samotij for our fruitful conversations. We would also like to thank the referees for their useful comments, which improved the presentation of the paper. This material is based upon work supported by NSF CAREER Grant DMS-0745185 , UIUC Campus Research Board Grant 09072 , and OTKA Grant K76099 . The second author acknowledges support from National Science Foundation grant DMS 08-38434 “EMSW21-MCTP: Research Experience for Graduate Students”.

PY - 2010/12/28

Y1 - 2010/12/28

N2 - 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.

AB - 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.

KW - Online Ramsey-games

KW - Ramsey number

KW - Random graphs

KW - Triangle-free

UR - http://www.scopus.com/inward/record.url?scp=77957985900&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77957985900&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2010.09.007

DO - 10.1016/j.disc.2010.09.007

M3 - Article

AN - SCOPUS:77957985900

SN - 0012-365X

VL - 310

SP - 3653

EP - 3657

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 24

ER -