Online Ramsey games for triangles in random graphs

In the online FF-avoidance edge-coloring game with rr colors, a graph on nn 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 FF. Let N0(F,r,n)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=K3F=K3, the order of magnitude of N0(F,r,n)N0(F,r,n) is unknown for r≥3r≥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 nn vertices with mm edges is presented to the player to be rr edge-colored. We improve the upper bound for the online triangle-avoidance game with rr colors, providing the first result that separates the online threshold function from the offline bound for r≥3r≥3. This supports a conjecture of Marciniszyn, Spöhel, and Steger that the known lower bound is tight for cliques and cycles for all rr.