\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Anupam Prakash, Reto Sp\"ohel and Henning Thomas}
%
%
\medskip
\noindent
%
%
{\bf Balanced Online Ramsey Games in Random Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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\'{c}. We also prove a similar threshold result
for the vertex-coloring analogue of this game.

\bye