%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% AMSLaTeX file for the paper                                        %
% Ramsey Games Against a One-Armed Bandit                            %
% by E. Friedgut, Y. Kohayakawa, V. R\"odl,                          %
% A. Ruci\'nski, and P. Tetali                                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 09 Aug 2002 07:42:03am BRT yoshi@ime.usp.br>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{upref}
%\usepackage{refcheck}
\usepackage{latexsym}
%\usepackage{amsfonts}
%\usepackage{amsmath}
%\usepackage{srcltx}
\usepackage[colorlinks,backref]{hyperref}

\allowdisplaybreaks[2]

\newtheorem{thm}{Theorem}%[section]
\newtheorem{defn}[thm]{Definition}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{sublemma}[thm]{Sublemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{fact}[thm]{Fact}
\newtheorem{ex}[thm]{Example}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{prob}[thm]{Problem}
\newtheorem{question}[thm]{Question}
\newtheorem{claim}[thm]{Claim}
\newtheorem{remark}[thm]{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\cG{{\mathcal G}}
\def\cK{{\mathcal K}}
\def\cR{{\mathcal R}}
\def\cS{{\mathcal S}}
\def\cT{{\mathcal T}}
\def\EE{{\mathbb E}}
\def\PP{{\mathbb P}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\ykcomm#1{\marginpar{\small\textsf{yk:} #1}}
\def\ykcomm#1{}
\def\ykncomm#1{\marginpar{\small\textsf{yk:} #1}}
\def\ykncomm#1{}
\def\yknncomm#1{\marginpar{\small\textsf{yk:} #1}}
\def\yknncomm#1{}
\def\yktext#1{[\textsf{#1}]}
\def\yktext#1{}
\let\subset=\subseteq
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\Base{\mathop{{\rm Base}}\nolimits}
%\def\Irr{\mathop{{\rm Irr}}\nolimits}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\rho=\varrho
\let\epsilon=\varepsilon
\let\theta=\vartheta
\def\cB{{\mathcal B}}
\def\cW{{\mathcal W}}
\def\bfd{{\mathbf d}}
%\def\tsigma{{\widetilde\sigma}}
\def\tsigma{\sigma}
\def\rmL{{\mathrm L}}
\def\rmC{{\mathrm C}}
\def\({\left(}
\def\){\right)}
\let\:=\colon
\def\tF{{\widetilde F}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\title[Ramsey games \& one-armed bandits]%
{Ramsey Games Against a One-Armed Bandit}

\author[Friedgut]{Ehud Friedgut} \address{Einstein Institute of
  Mathematics, The Hebrew University of Jerusalem, Jerusalem, 91904, Israel}
\email{ehudf@math.huji.ac.il}
\author[Kohayakawa]{Yoshiharu Kohayakawa}
\address{Instituto de Matem\'atica e Estat\'{\i}stica, Universidade de S\~ao
  Paulo, Rua do Mat\~ao 1010, 05508--900~S\~ao Paulo, Brazil}
\email{yoshi@ime.usp.br}
\author[R\"odl]{Vojt\v ech R\"odl}
\address{Department of Mathematics and Computer Science, Emory University,
  Atlanta, GA 30322, USA} \email{rodl@mathcs.emory.edu}
\author[Ruci\'nski]{\\Andrzej Ruci\'{n}ski} \address{Faculty of Mathematics
  and Computer Science, Adam Mickiewicz University, Pozna\'n, Poland, and
  Department of Mathematics and Computer Science, Emory University, Atlanta,
  GA 30322, USA}
\email{rucinski@amu.edu.pl}
\author[Tetali]{Prasad Tetali} \address{School
  of Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332, USA}
\email{tetali@math.gatech.edu}
%
\thanks{The second author was partially supported by MCT/CNPq through ProNEx
  Programme (Proc.\ CNPq 664107/1997--4) and by CNPq (Proc.~300334/93--1
  and~468516/2000--0).  The third author was partially supported by NSF
  Grant~0071261.  The fourth author was supported by KBN grant 2~PO3A~015~23.
  The collaboration between the second and third authors is supported by a
  CNPq/NSF cooperative grant.  The last author was partially supported by the
  NSF grant DMS-0100298}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subjclass{%Primary 05C55, % Generalised Ramsey theory
  05C80,                   % Random graphs
  91A43,                   % Games involving graphs
  Secondary:
%  91A46,                   % Combinatorial games
  05C55,                   % Generalized Ramsey theory
  91A60}                   % Probabilistic games
\keywords{Random graphs, Ramsey games, thresholds}
%  regular pairs, Szemer\'edi's regularity
%  lemma}
%\date{Working draft, not for circulation.  Copy produced on \today}
\date{Copy produced on \today}
%\date{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
  We study the following one-person game against a random graph: the Player's
  goal is to $2$-colour a random sequence of edges $e_1,e_2,\dots$ of a
  complete graph on~$n$ vertices, avoiding a monochromatic triangle for as
  long as possible.  The game is over when a monochromatic triangle is
  created.  The online version of the game requires that the Player should
  colour each edge when it comes, before looking at the next edge.

  While it is not hard to prove that the expected length of this game is
  about~$n^{4/3}$, the proof of the upper bound suggests the following
  relaxation: instead of colouring online, the random graph is generated in
  only two rounds, and the Player colours the edges of the first round before
  the edges of the second round are thrown in.  Given the size of the first
  round, how many edges can there be in the second round for the Player to be
  likely to win?  In the extreme case, when the first round consists of a
  random graph with~$cn^{3/2}$ edges, where~$c$ is a positive constant, we
  show that the Player can win with high probability only if
  \textit{constantly} many edges are generated in the second round.
\end{abstract}

\maketitle
\thispagestyle{empty}
% \bgroup
% %\vspace{-.8truecm}
% \small
% \tableofcontents
% \thispagestyle{empty}
% \egroup

\section{Introduction}

In this paper, we study \textit{Ramsey one-person triangle avoidance games
  against a random graph}.  In all versions of our game, the goal of the
player, called throughout \textit{the Painter}, is to colour randomly
generated edges, using a given number of colours, without creating a
monochromatic triangle.  The object of this paper is to study how long the
Painter can `survive', that is, stay in the game.
%
%Informally, the \textit{length} of the game is the
%maximum number of edges on which the Painter can win with large probability.
%
We distinguish three versions of the game: \textit{online},
\textit{two-round}, and \textit{offline}.\ykcomm{Is it `online' or `on-line'?
  Changed `static' to `offline'}

\subsection{The three games}
\label{sec:three_games}
Let us discuss the variants of our game separately.

\subsubsection{The online game}
In the \textit{online} version of our game, the Painter receives a random
sequence of edges, and she has to colour
each edge as it comes, avoiding monochromatic triangles as long as possible.

It turns out that, when the number of colours available to the Painter
is~$r=2$, this game is quite easy to analyse; indeed, a fairly simple `local'
argument shows that this game typically lasts for~$\Theta(n^{4/3})$ steps.

We observe that the length of the game is not so sharply determined.  When the
Painter has seen only~$o(n^{4/3})$ edges, she is essentially certain to be
safe; she is most unlikely to survive up to~$\omega n^{4/3}$ edges, for
any~$\omega$ with~$\omega=\omega(n)\to\infty$ as~$n\to\infty$; but, for
any~$c>0$, she has probability bounded away from~$0$ and~$1$ of surviving up
to~$cn^{4/3}$ edges.\ykcomm{I weakened the assertion here.  It used to be that
  there is some limit $0<\theta=\theta(c)<1$ for the probability of survival}

\subsubsection{The two-round game}
What happens if the Painter has a \textit{mercy period}?  That is, suppose she
is allowed \textit{not} to colour the first, say, $N_0$~edges online, but may
wait to see \textit{all of them} before committing herself to the colour of
those edges.  Clearly, she should be able to survive longer, because her
initial colouring can be cleverer.  Moreover, instead of switching back to the
online version after the mercy period of~$N_0$ edges, let us suppose that
another~$N_1$ random edges are now presented to the Painter.  If she is able
to extend her initial colouring of the~$N_0$ edges to the union of the~$N_0$
and the~$N_1$ edges still avoiding monochromatic triangles, she wins;
otherwise, she loses.  This is the \textit{two-round} version of our game.

We shall analyse the two-round game with~$N_0=cn^{3/2}$, for~$c$ a small
positive constant.  (We shall see in a moment why this is the interesting
choice for~$N_0$.)  The result here is that, with such a value of~$N_0$, if
the Painter has~$r=2$ colours available, then typically she can win only
if~$N_1=O(1)$: for any~$N_1=N_1(n)$ that tends to infinity, the probability
that the Painter wins tends to~$0$.

We shall also show that, if~$N_0=cn^{3/2}$ and~$r=3$ colours are available,
then the breakpoint for~$N_1$ is of order~$n$: if~$N_1=o(n)$, then the Painter
typically wins; if~$N_1=\omega n$, where~$\omega=\omega(n)$ tends to infinity,
then the Painter typically loses.  If~$N_1=\Theta(n)$, then she wins with
probability bounded away from~$0$ and~$1$.\ykcomm{Again, I weakened the
  assertion to `bounded away from...'} Note that, as in the online game, the
transition is not sharp.

%We finally turn to the \textit{offline} version of our game.
%Here it will be more convenient to consider the binomial model~$G(n,p)$ for
%random graphs.

\subsubsection{The offline game}
In the offline game, an $n$-vertex graph~$G(n,N)$ with a fixed number of
edges~$N=N(n)$ is generated uniformly at random and is presented to the
Painter; her task is to colour the edges of~$G(n,N)$ avoiding monochromatic
triangles.

The reader familiar with the theory of random graphs will immediately see that
the analysis of this game amounts exactly to determining the threshold for the
Ramsey property~$\cR_r$, which consists of all graphs such that every
$r$-colouring of their edges results in a monochromatic triangle.

The threshold for the property~$\cR_r$ has been investigated for some time
now.  In particular, it has been proved  that there exist constants~$c_r$
and~$C_r$ such
that
\begin{equation}
  \label{eq:basic_threshold}
  \lim_{n\to\infty}\PP[G(n,N)\in\cR_r]
  =
  \begin{cases}
    1   &\text{if $N>C_rn^{3/2}$}\\
    0   &\text{if $N<c_rn^{3/2}$.}
  \end{cases}
\end{equation}
The above threshold of~$n^{3/2}$ was verified for~$r=2$
in~\cite{luczak92:_ramsey} (see also~\cite{frankl86:_large_k}), and then
proved for arbitrary~$r\ge2$ in~\cite{rodl94}.  It is interesting to note that
the dependence on~$r$ is not present in the exponent of~$n$, but only in the
constants.

Returning to the case~$r=2$, the current proofs leave a wide gap between~$c_2$
and~$C_2$.  Using a criterion from~\cite{friedgut99:_sharp} for the existence
of sharp thresholds, that gap was recently annihilated in~\cite{friedgut02}.
In the usual parlance, the Ramsey property~$\cR_2$ admits a \textit{sharp
  threshold}.  We shall come back to this in
Section~\ref{sec:sharp_threshold}.  Note that the existence of a sharp
threshold for~$\cR_2$ means that the offline game for~$r=2$ colours has a
sharply determined value, unlike the online and the two-round games.

\subsubsection{Further remarks}
It is the result in~\eqref{eq:basic_threshold} that suggests the investigation
of the two-round game with~$N_0$ of order~$n^{3/2}$.  Note that the game would
be trivial if~$N_0>C_rn^{3/2}$, for in that case the chances of the Painter
surviving even the first round are rather slim.  On the other hand, if~$r=2$
and~$N_0=cn^{3/2}$ with~$c<c_r$, then it first seems that the Painter should
be happy, because she has a very good chance of being able to colour the edges
of the first round.  However, our result (Theorem~\ref{thm:2r2c} below) shows
that, at least for $r=2$, her happiness is short-lived: \textit{regardless of
  how small~$c$ is}, the fact that she has to colour those~$N_0$ edges
\textit{before seeing the final graph} makes it very unlikely that she will
succeed in colouring even as few as, say, $N_1=\log\log\log n$ further edges!
This is in contrast to the fact that, if~$N_0+N_1<c_rn^{3/2}$, then,
typically, $G(n,N_0+N_1)$~may be $2$-edge-coloured avoiding monochromatic
triangles (see~\eqref{eq:basic_threshold}).

We mention in passing that, in Section~\ref{sec:sharp_threshold}, we shall
attempt to explain how the two-round version of our game naturally arose from
a technical part of the proof of the existence of a sharp threshold
for~$\cR_2$.

Interestingly enough, both the two-round and online versions of our Ramsey
game are much more sensitive to the number of colours available to the Painter
than the offline one is.  Recall that, for example, in the two-round game,
while for~$r=2$ colours the survival time is~$O(1)$, for~$r=3$ colours the
survival time is of order~$n$.  For the online, $3$-colour game, we have
a lower bound of roughly~$n^{7/5}$ for its length, which is much larger than
for two colours.  At this point, we do not have a matching upper bound for the
$3$-colour game.

\subsection{Organization}
\label{sec:organize}
This paper is organized as follows.  In Section~\ref{sec:sharp_threshold} we
briefly discuss the proof of the existence of a sharp threshold for the
property~$\cR_2$, and its relation to this paper.  In
Section~\ref{sec:main_game_results}, we state and prove our results on Ramsey
games.  As it turns out, most of the work will go into proving a certain
delicate lemma (Lemma~\ref{cor:3_colours});
Section~\ref{sec:proof_of_3_colours} will be entirely devoted to proving this
lemma.  In Section~\ref{sec:conclude}, we briefly discuss some open problems.

\subsection{Notation and terminology}
\label{sec:notation}
Our notation is fairly standard.  We let~$[n]=\{1,\dots,n\}$.  We
write~$[X]^k$ for the family of $k$-element subsets of~$X$.  Let~$G=(V(G),E(G))$
be a graph.  If~$x$ is a vertex of~$G$, then~$N_G(x)=N(G;x)$ denotes
the neighbourhood of~$x$ in~$G$. We write $\deg_G(x)=|N_G(x)|$ and
$\Delta(G)=\max\{\deg_G(x)\:x\in V(G)\}$.
If~$U\subset V(G)$, we write~$G[U]$
for the subgraph of~$G$ induced by~$U$.  Thus,
$E(G[U])=E(G)\cap[U]^2$. We put~$e_G(U)$ for $|E(G[U])|$, the number
of edges induced by~$U$ in~$G$, and $N_G(U)=\bigcup_{x\in U}N_G(x)$.

If~$U$, $W\subset V(G)$ are disjoint,
then~$G[U,W]$ stands for the bipartite graph with vertex classes~$U$
and~$W$ naturally induced by~$U$ and~$W$ in~$G$.  We write~$E_G(U,W)$
for the set of edges of~$G$ with one endvertex in~$U$ and the other
in~$W$. That is~$E_G(U,W)=E(G[U,W])$.  We let~$e_G(U,W)=|E_G(U,W)|$.
We sometimes identify a graph with its edge set.

We define, for a graph~$F$, the
\textit{base graph}~$\Base(F)$ on the vertex set~$V(F)$ as follows: a
pair~$e$ of vertices of~$F$ is an edge of~$\Base(F)$ if it forms a
triangle with two edges of~$F$.
A colouring of the edges of a graph will be called \textit{proper} if it
does not contain a monochromatic triangle.

We shall consider the three standard models for random graphs:\ykcomm{added
  the random graph models here, including the observation that if you stop a
  process at time $t$ you have a $G(n,t)$; later, a reference to this section
  is made} the binomial random graphs~$G(n,p)$, the uniform random
graphs~$G(n,N)$, and the random graph process~$G_0\subset\dots\subset
G_{n\choose2}$, which naturally corresponds to random
permutations~$e_1,\dots,e_{n\choose2}$ of the edges of the complete graph
on~$[n]$.  In particular, if we stop a random graph process at time~$t$, we
obtain a random graph in the uniform model~$G(n,t)$.  When convenient, we
switch between these models without discussion. A rule of thumb is that most
results can be ``translated'' back and forth between the binomial and uniform
models, provided $N\sim p\binom n2$.  For more on the (asymptotic) equivalence
of these models and on random graphs in general, we refer the reader
to~\cite{BBf} and~\cite{janson00:_random_graph}. Another feature we will use
is the monotonicity.  If a graph property $Q$ is increasing (preserved under
edge addition), and $p_1\le p_2$, then $\PP(G(n,p_1)\in Q)\le\PP(G(n,p_2)\in
Q)$.

Most of the time, we have a parameter~$n$ and we are interested in the case in
which~$n\to\infty$.  As usual, we use the term `asymptotically almost surely'
(a.a.s.)\ to mean `with probability tending to~$1$ as~$n\to\infty$'.
Therefore, we often tacitly assume that~$n$ is large enough (for instance, for
some inequalities to hold).  Also, we drop the $\lfloor\;\;\rfloor$
and~$\lceil\;\;\rceil$ from our formulae when they are not important.  This
will simplify the exposition considerably.

Our logarithms are natural logarithms.

\subsubsection*{Acknowledgements}
We thank Svante Janson for his interest and suggestions.  Part of this
work was done when some of the authors were at the meeting
\textit{Combinatorics, Probability, and Computing}, at the
Mathematisches Forschungsinstitut Oberwolfach.\ykcomm{added
  Oberwolfach; I'll check the name of the meeting}

\section{Sharp thresholds}
\label{sec:sharp_threshold}
The questions considered in this paper arose naturally during the work
on~\cite{friedgut02}, which studies the notion of sharp threshold for the
property~$\cR_2$.  We briefly outline the ideas that arise in that paper in
order to explain the background to the present work.  However, the remainder
of this paper does \textit{not} depend on this section.

Recall that~$\cR_2$ consists of all graphs such that every $2$-colouring of
their edges results in a monochromatic triangle.  Below, we refer to the
graphs in~$\cR_2$ as \textit{Ramsey graphs}.  The main result
in~\cite{friedgut02} is the following theorem, asserting that property~$\cR_2$
admits a sharp threshold.
\begin{thm}
  \label{thm:sharp}
  There exists a function~$b=b(n)=\Theta(1)$ such that for all~$\epsilon>0$ we have
  \begin{equation*}
    \lim _{n \to \infty}\PP[G(n,p)\in\cR_2] =
    \begin{cases}
      1 &\text{if $p>(1+\epsilon)b(n)/\sqrt{n}$}\\
      0 &\text{if $p<(1-\epsilon)b(n)/\sqrt{n}$.}
    \end{cases}
  \end{equation*}
\end{thm}

The proof of Theorem~\ref{thm:sharp} is based on a consequence of Friedgut's
criterion from~\cite{friedgut99:_sharp}, which we now discuss.  Let~$M$ be an
arbitrary, fixed balanced graph with average degree~$4$, and let~$M^*$ be a
random copy of~$M$ in~$K_n$.  It follows from~\cite{friedgut99:_sharp} that,
in order for~$\cR_2$ to have a sharp threshold, it is sufficient to prove the
following:
\begin{enumerate}
\item[(*)]{\sl For any choice of the constants~$c$, $C$, $\alpha$,
    and~$\xi>0$, and for any~$M$ as above, there is a graph property~$\cG$
    such that
    \begin{enumerate}
    \item[(\textit{a})] if~$p=p(n)$ satisfies
      ${c/\sqrt n}\leq p\leq{C/\sqrt n}$,
      then $G(n,p)\in\cG$ a.a.s.,
    \end{enumerate}
    and, moreover, such that, for all $n$-vertex graphs~$G\in\cG$ with
    sufficiently large~$n$,
    \begin{enumerate}
    \item[(\textit{b})]if $\PP[G\cup M^*\in\cR_2]>\alpha$, then
      $$
      \PP[G\cup G(n,\xi p)\in\cR_2]\to 1\text{ as }n\to\infty.
      $$
    \end{enumerate}
  }
\end{enumerate}

Note that, roughly speaking, the implication in~(\textit{b}) means that
every~$G\in\cG$ is such that, if~$G$ may be turned with positive probability
into a Ramsey graph by adding a random copy of~$M$, then~$G$ turns a.a.s.\ 
into a Ramsey graph when~$(1+o(1))\xi p{n\choose2}$ edges are sprinkled
randomly.

We recall that~$M$ is a small graph, and hence the addition of~$M^*$ to~$G$ is
a `local' change, whereas adding~$G(n,\xi p{n\choose2})$ is `global'.
Moreover, observe that~(\textit{b}) is non-trivial only when~$G\notin\cR_2$.
Also, because of our conditions on~$M$, it can be proved that~$M\notin\cR_2$
(see~\cite{friedgut02,kurek02:_ramsey}).

Let us now say a few words about the verification of Friedgut's condition~(*).
One takes for~$\cG$ a certain well-defined pseudorandom property of graphs
with~$n$ vertices and~$(1+o(1))p{n\choose2}$ edges
(see~\cite[Definition~6.1]{friedgut02})\yknncomm{definition number
  from~\cite{friedgut02} is correct?} and one assumes that the assumption in
implication~(\textit{b}) holds.  As observed above, one may assume
that~$G\notin\cR_2$ and we have~$M\notin\cR_2$.  A fairly complicated and
lengthy argument, involving a tailor-cut regularity lemma
(see~\cite{friedgut02}), leads to the conclusion that, for some~$\lambda>0$,
there exists a `small' family~$\cK$ of `large' subgraphs of~$G$ such that
there is always a monochromatic copy of a member of~$\cK$ in every proper
colouring of the edges of $G$.  More precisely, the family~$\cK$ is such that
\begin{enumerate}
\item[(\textit{i})]$|\cK|=2^{o(n^{3/2})}$,
\item[(\textit{ii})]for all $K\in\cK$, we have~$|E(K)|>\lambda|E(G)|$,
\end{enumerate}
and, most importantly,
\begin{enumerate}
\item[(\textit{iii})]for every proper $2$-colouring of the edges of~$G$, there
  is a~$K\in\cK$ that is monochromatic.
\end{enumerate}
Now we observe that, in order to prove the conclusion of~(\textit{b}), it is
enough to find, for every~$K\in\cK$, a triangle~$T=T(K)\subseteq G(n,\xi p)$,
such that~$T\subseteq\Base(K)$, \textit{i.e.}, a triangle~$T$ such that each
of the edges of~$T$ forms a triangle together with a path of length two
in~$K$. (Indeed, in this case, if~$K$ is monochromatic, there is no way to
extend the colouring of~$G$ to a proper colouring of~$G\cup G(n,\xi p)$.)

To establish the existence of~$T=T(K)$ above, we first define the following
property of a graph~$G$:
\begin{enumerate}
\item[(\dag)]Given two real numbers~$0<\lambda<1$ and~$0<a<1/6$, we say
  that~$G$ has property $\cT(\lambda,a)$ if, for any subgraph~$F$ of~$G$ with
  at least~$\lambda|E(G)|$ edges, the graph~$\Base(F)$ contains at
  least~$a|V(G)|^3$ triangles.
\end{enumerate}

Since the~$K\in\cK$ has at least~$\lambda|E(G)|$ edges (it
satisfies~(\textit{ii}) above), if~$\cT(\lambda,a)$ holds for~$G\in\cG$, then
we may conclude that every~$K\in\cK$ is such that~$\Base(K)$ contains at
least~$a|V(G)|^3$ triangles.  As it turns out (see the following lemma), we
may \textit{define}~$\cG$ such that~(\textit{a}) holds and~$\cT(\lambda,a)$
holds for every~$G\in\cG$.

\begin{lemma}
  \label{lem:pro1}
  For any~$c>0$ and $\lambda>0$, there exists~$a>0$ such that if~$p\ge c/\sqrt
  n$ then a.a.s.\ the random graph~$G(n,p)$ has property $\cT(\lambda,a)$.
\end{lemma}

Lemma~\ref{lem:pro1} allows us to require that~$\cT(\lambda,a)$ should hold
for all~$G\in\cG$.

Now we are ready to establish the existence of~$T=T(K)$ for all~$K\in\cK$.
Indeed, for any fixed~$K\in\cK$, the fact that~$\Base(K)$ contains at
least~$a|V(G)|^3$ triangles implies, via Janson's
inequality~\cite{JansonLuczakRucinski}, that, with probability
$1-2^{-\Theta(n^{3/2})}$, there is a triangle~$T(K)$ in $\Base(K)\cap G(n,\xi
p)$.  Since~(\textit{i}) holds, we have that a suitable triangle~$T=T(K)$ does
exist a.a.s.\ for every~$K\in\cK$.  The conclusion of~(\textit{b}) now follows
from~(\textit{iii}).

To summarize, the convergence
$$
\PP[G\cup G(n,\xi p)\in\cR_2]\to 1
$$
follows indirectly from a statement about the two-round Ramsey game against
a random graph: the proof involves extending proper colourings of graphs of
size~$\Theta(n^{3/2})$.  This explains why Lemma~\ref{lem:pro1} and a related
result, Lemma~\ref{cor:3_colours} given below, are useful tools in studying
such games.

\section{Ramsey triangle avoidance games}
\label{sec:main_game_results}
This section contains our main results.  In Section~\ref{sec:online}
below, we prove a relatively simple result for the online version of
the Ramsey game.  In~Section~\ref{sec:two-round}, we state two results
on the two-round game, together with their proofs, pending a
major\ykcomm{not sure about usage of `pending'; changed `main' to
  `major'} technical lemma, Lemma~\ref{cor:3_colours}, which will be
proved in Section~\ref{sec:proof_of_3_colours}.

\subsection{The online game}
\label{sec:online}
Consider the random graph process
$$
e_1,\dots,e_{\binom n2}
$$
on~$n$ vertices (see Section~\ref{sec:notation}), revealing its edges one
by one, and the following one-person game related to it.  The Painter's task
is to $2$-colour the edges online, with colours red and blue, say, and not to
create a monochromatic triangle for as long as she can.  Here \textit{online}
means that the Painter has to decide on the colour of~$e_i$ before~$e_{i+1}$
is generated.  The game is over when a monochromatic triangle is created (this
does happen eventually if~$n\geq6$).  For how long can she stay in the game with
probability approaching~$1$ as~$n\to\infty$?

More formally, for each strategy~$\pi$ of the Painter, let $X_\pi$ be the
length of the game, \textit{i.e.}, $X_{\pi}$~is the largest index~$N$ such
that~$e_1,\dots,e_N$ contains no monochromatic triangle.  The goal of the game
is to choose a strategy that maximizes the expectation $\EE(X_\pi)$.  By a
\textit{strategy} we mean a complete set of rules assigning a colour to the
next edge.

Since~$e_1,\dots,e_N$ is exactly the random graph~$G(n,N)$, clearly,
by~\eqref{eq:basic_threshold}, an upper bound on the expected duration of the
game is~$C_2n^{3/2}$.  We shall soon show that the threshold for the length of
the online game is in fact much smaller.

A crucial tool in our investigation is the base graph~$\Base(F)$ of a
graph~$F$.  Recall that a pair~$e$ of vertices of~$F$ is an edge in~$\Base(F)$
if it forms a triangle with two edges of~$F$.  Now consider an online
$2$-colouring of the edges~$e_1,\dots,e_{n\choose2}$.  Let~$R_i$ and~$B_i$ be
the sets of the edges~$e_j$ ($j\leq i$) coloured so far with colours red and
blue, respectively.  The Painter is stuck if and only if
$$
e_{i+1}\in\Base(R_i)\cap\Base(B_i).
$$
Similarly, the game is bound to be over by time~$j$\ykcomm{changed
  to `by time $j$'} if for some~$i<j$, the intersection of the set of
edges $\{e_{i+1},\dots,e_j\}$ with~$\Base(R_i)$ (or with~$\Base(B_i$))
contains a triangle.

Let us begin with a trivial lower bound.  As long as~$N=o(n^{6/5})$,
there is a.a.s.\ no copy of a diamond in~$e_1,\dots,e_N$, that is,
a~$K_4$ with an edge omitted, and the Painter never gets stuck until
the $N$th edge, since a.a.s.
$$
e_{i+1}\not\in\Base(R_i)\cap\Base(B_i)
$$
for each $i<N$.

But she can do better: as long as $N=o(n^{4/3})$ a.a.s.\ neither a
copy of~$K_4$ nor a copy of the pyramid graph (see
Figure~\ref{fig:pyramid}) has emerged, and so~$\Base(G(n,N))$ does not
contain a triangle.  Hence the greedy strategy~$\pi_0$ of colouring
each edge red, unless such a move would create a red~$K_3$, is
successful.  Indeed, $\Base(R_N)$, which is a subgraph
of~$\Base(G(n,N))$, is triangle-free, and no blue triangle will be created.  We
have just proved that a.a.s.~$X_{\pi_0}>n^{4/3}/\omega$ for
any~$\omega=\omega(n)$ with~$\omega\to\infty$.

\begin{figure}[ht]
%\includegraphics[scale=.5]{ppp2.eps}
\begin{picture}(0,0)%
\includegraphics[scale=.5]{ppp2}%
\end{picture}%
%\setlength{\unitlength}{3947sp}%
\setlength{\unitlength}{1973.5sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(9016,2116)(1718,-3594)
\end{picture}

\caption{The pyramid, the enhanced pyramid, and the double pyramid}
\label{fig:pyramid}
\end{figure}\ykcomm{are these names for the graphs appropriate?}

Quite surprisingly, $n^{4/3}$~is the right threshold for the length of the
random online triangle avoidance game.

\begin{thm}
  \label{thm:4/3}
  For every~$\omega$ with~$\omega=\omega(n)\to\infty$ as~$n\to\infty$ and for
  every strategy~$\pi$ of the Painter, a.a.s.~$X_\pi<\omega n^{4/3}$.
\end{thm}
\begin{proof}
  We relax the online regime by allowing a \textit{mercy period} of
  $N_0=n^{4/3}$ steps; \textit{i.e.}, only after that many edges are
  generated, do they have to be coloured by the Painter.  We shall argue that
  no matter how they are coloured, the Painter loses a.a.s.\ after
  another~$(\omega-1)n^{4/3}$ edges.  This is nothing else but a two-round
  exposure technique (see~\cite{janson00:_random_graph}), with a colouring in
  between.

  The aim is to show that a.a.s.\ every subgraph of~$G(n,N_0)$ with at least
  half of the edges (the majority colour) has at least~$\Omega(n^2)$ triangles
  in its base.  Then, by the second moment method, any~$\omega n^{4/3}$
  additional random edges will a.a.s.\ contain at least one of these triangles
  and the game will be over.

  A.a.s.\ the number of copies of~$K_{2,3}$ in~$G(n,N_0)$, denoted
  by~$X(K_{2,3})$, is smaller than, say, $n\log n$.  Let~$R$ be the majority
  colour in~$G(n,N_0)$ and let~$d_1,\dots,d_n$ be the degree sequence in~$R$.
  Then the number of triangles in the base of~$R$ is at least\ykcomm{slightly
  changed}
  $$
  \sum_{i=1}^n\binom{d_i}3-X(K_{2,3})
  \geq n{N_0/n\choose3}-X(K_{2,3})=\Omega(n^2),
  $$
  where the last equation holds a.a.s.
\end{proof}

The reader will have no difficulty in verifying that the proofs above show
that, for any~$c>0$, the Painter has probability bounded away from~$0$ and~$1$
of surviving up to~$cn^{4/3}$ edges.\ykcomm{remark added}

With three colours at hand the Painter can survive quite a bit longer.
The painter may use the natural greedy strategy, say~$\pi_1$, which
colours an edge red if possible, otherwise blue if possible, and
finally yellow if none of red and blue will do.\ykcomm{added
  definition of $\pi_1$} Using~$\pi_1$, the painter gets stuck only if
a copy of the double pyramid, or of the enhanced pyramid (see
Figure~\ref{fig:pyramid}), or of~$K_5$ with an edge omitted has
emerged.  Since such subgraphs a.a.s.\ do not appear in the random
graph with~$o(n^{7/5})$ edges, we obtain
that~$\PP(X_{\pi_1}>n^{7/5}/\omega)\to 1$.  However, we do not know
whether this is the right threshold.

\subsection{The two-round game}
\label{sec:two-round}
The proof of Theorem~\ref{thm:4/3} bridges the online and the two-round game,
which we now define formally.  Given two integers~$N_0$~and~$N_1$, first,
$N_0$~edges are generated randomly (let~$G_0=G(n,N_0)$ be the graph defined by
these edges), and the Painter colours them \textit{properly} with~$r$ colours
(if possible),\ykcomm{added `if possible'} that is, avoiding monochromatic
triangles.  Then a second round of~$N_1$ random edges (graph~$G_1$) is thrown
in and the Painter wins if her colouring of~$G_0$ has an extension to a proper
colouring of~$G_0\cup G_1$ (if~$G_0$ cannot be properly coloured, the Painter
already lost at that stage).\ykcomm{added this comment on Ramsey $G_0$}

For a given strategy~$\pi$ of the Painter, let~$P_\pi(r,N_0,N_1)$ be the
probability that the Painter wins the game when using~$\pi$.  Here, by a
\textit{strategy}, we mean an assignment of an $r$-edge-colouring to every
graph with $N_0$ edges.  Thus, the goal of the Painter is to find a
strategy~$\pi$ that maximizes~$P_\pi(r,N_0,N_1)$.  Let
$$
P^*(r,N_0,N_1)=\max_\pi P_\pi(r,N_0,N_1).
$$

The above proof of Theorem~\ref{thm:4/3} gives that $P^*(2,n^{4/3},\omega
n^{4/3})=o(1)$, because the base of the majority colour in~$G_0=G(n,n^{4/3})$
contains~$\Theta(n^2)$ triangles.  This simple argument may be extended to a
wider range of~$N_0$ (for~$r=2$), namely,
$$
n^{7/6}\le N_0\le cn^{3/2},
$$
where here and below~$c$ is always assumed to be so small that
$$
\PP(G(n,cn^{3/2})\in{\cR}_2)=o(1).
$$
Indeed, along similar lines,\ykcomm{rephrased} one may easily prove
that there are~$\Theta(N_0^3/n^2)$ triangles in the base graph of
the majority colour of~$G_0=G(n,N_0)$, and consequently, arguing as in
the proof of Theorem~\ref{thm:4/3}, we have
$$
P^*(2,N_0,\omega n^{8/3}/N_0)=o(1).
$$
In particular, in the most extreme case, we obtain that the number of
triangles in the base graph of the majority colour of~$G_0=G(n,cn^{3/2})$ is
$\Theta(n^{5/2})$, and thus $P^*(2,cn^{3/2},\omega n^{7/6})=o(1)$.

Using Lemma~\ref{lem:pro1} with~$\lambda=1/2$ and with~$F$
consisting of the edges coloured by the majority colour, we can
improve the above and conclude that in fact a.a.s., for any
$2$-edge-colouring of~$G(n,cn^{3/2})$, the number of triangles in the
base graph of the majority colour is of maximal possible
order~$\Theta(n^3)$.  By the second moment method this yields that
$$
P^*(2,cn^{3/2},\omega n)=o(1)
$$
(a triangle is needed in the base of one colour).  To improve this any
further we need to find a stronger tool.

As we have just seen, Lemma~\ref{lem:pro1}, put in the colouring context, says
that the base of the majority colour is rich in triangles.  A powerful
extension of that result, Lemma~\ref{cor:3_colours} below, which is the main
technical\ykcomm{added the qualifier `technical'} result of this paper,
implies that the same is true for the intersection of the bases of two
colours, provided the colouring is proper.  This result not only settles the
two-round game for $r=2$, but also for $r=3$, the other interesting case.

\begin{lemma}
  \label{cor:3_colours}
  For all~$c>0$, there are constants~$\alpha$ and~$\beta>0$ such that
  with~$p=c/\sqrt n$ the random graph $G=G(n,p)$ a.a.s.\ satisfies the
  following property.  For every proper $3$-colouring $E(G)=R\cup B\cup Y$ of
  the edges of~$G$, there are two colours, say~$R$ and~$B$, such that, letting
  \begin{equation}
    \label{eq:I_def}
    I=\Base(R)\cap\Base(B),
  \end{equation}
  we have
  \begin{enumerate}
  \item[(\textit{i})]$|E(I)|\geq\alpha n^2$
  \end{enumerate}
  and, in fact,
  \begin{enumerate}
  \item[(\textit{ii})]the graph~$I$ contains at least~$\beta n^3$ triangles.
  \end{enumerate}
\end{lemma}

\begin{remark}
  \label{rem:L2_and_L4}\sl
  Note that Lemma~\ref{lem:pro1} is \textit{not} a special case of the
  seemingly stronger Lemma~\ref{cor:3_colours}.  In Lemma~\ref{lem:pro1} the
  parameter~$\lambda$ may be arbitrarily small, while in
  Lemma~\ref{cor:3_colours} the assumption that the colouring must be proper
  sets an implicit lower bound on the size of the second largest colour
  {\rm(}see~\eqref{eq:R_B_large}{\rm)}.  In particular, it seems that
  Lemma~\ref{cor:3_colours} cannot replace Lemma~\ref{lem:pro1} in the proof
  of Theorem~\ref{thm:sharp} in~\cite{friedgut02}.

  Nevertheless, the proof of Lemma~\ref{cor:3_colours}, besides some
  new ideas, uses the ideas from the proof of Lemma~\ref{lem:pro1}.
  The relation between the proofs of Lemmas~\ref{lem:pro1}
  and~\ref{cor:3_colours} is briefly discussed in
  Section~\ref{rem:pf_of_lem_pro1}.
\end{remark}

Taking Lemma~\ref{cor:3_colours}
 for granted, we are ready to state and prove
our results for the two-round game.

\begin{thm}
  \label{thm:2r2c}
  For any~$\omega$ with~$\omega=\omega(n)\to\infty$ as~$n\to\infty$, we have
  $$
  P^*(2,cn^{3/2},\omega)=o(1).
  $$
\end{thm}
\begin{proof}
  This follows immediately from Lemma~\ref{cor:3_colours}(\textit{i}) (with
  $Y=\emptyset$), since a.a.s.\ at least one of the~$\omega$ new edges will
  fall into~$I$.
\end{proof}

Finally, let us consider the two-round game for~$r>2$
and~$N_0=cn^{3/2}$.  If~$r\ge4$, then a trivial conservative strategy
is to use only two colours for~$G_0$ and then another two colours for
$G_1$.  This, together with the threshold result from~\cite{rodl94}
settles the game at~$\Theta(n^{3/2})$, \textit{i.e.}, there exist
constants~$b$ and~$B>0$ for which we have
\begin{equation*}
  \lim_{n\to\infty}P^*(r,cn^{3/2},N_1)
  =
  \begin{cases}
    1  &\text{if $N_1<bn^{3/2}$}\\
    0  &\text{if $N_1>Bn^{3/2}$}.
  \end{cases}
\end{equation*}
In the remaining case~$r=3$, we have the following, complete solution.

\begin{thm}
  \label{thm:r=3}
  We have
  \begin{equation*}
    \lim_{n\to\infty}P^*(3,cn^{3/2},N_1)
    =
    \begin{cases}
      1  &\text{if $N_1\ll n$}\\
      0  &\text{if $N_1\gg n$}.
    \end{cases}
    \end{equation*}
\end{thm}
\begin{proof}
  The `$1$-statement', that is, the fact that $P^*(3,cn^{3/2},N_1)\to1$
  as~$n\to\infty$, follows by using only two colours for~$G_0$, and then
  exclusively the third colour for~$G_1$.  As long as $N_1=o(n)$, a.a.s.\
  there will not be any triangles in~$G_1$.  The $0$-statement follows from
  the second moment method\ykcomm{Janson was mentioned here,
  but 2nd moment should be enough.  \textbf{Do we agree?}} and
  Lemma~\ref{cor:3_colours}(\textit{ii}).
%For the 0-statement,
%we may apply ... and Janson's inequality~\cite{JansonLuczakRucinski} (see
%also~\cite{janson00:_random_graph}).
\end{proof}

We remark that the proof above shows that~$P^*(3,cn^{3/2},c'n)$ is bounded
away from~$0$ and~$1$ for any~$c'>0$.\ykcomm{remark added}

\section{Pairs at distance two in red and blue}
\label{sec:proof_of_3_colours}
Our aim in this section is to prove Lemma~\ref{cor:3_colours}.  On the
way we shall come close to proving Lemma~\ref{lem:pro1} (see
Section~\ref{rem:pf_of_lem_pro1}).  However, we refer the reader
to~\cite{friedgut02} for the complete proof of Lemma~\ref{lem:pro1}.

Let us introduce a piece of terminology.  Let~$\rho$ and~$d$ be positive
reals.  We say that a graph~$H$ is \textit{$(\rho,\tau)$-dense} if, for all
$U\subseteq V(H)$ with $|U|\ge \rho|V(H)|$, we have
$$
e_H(U)\ge \tau\binom{|U|}2.
$$
%An easy averaging argument shows that, when verifying this property,
%it\ykncomm{still left, but probably can omit this comment about these special
%  equality witnesses} suffices to check only all subsets~$U$ of
%cardinality~$|U|=\lceil\rho|V(H)|\rceil$.

We now state a strengthening of Lemma~\ref{cor:3_colours}, which,
together with an easy property of $(\rho,\tau)$-dense graphs, implies
Lemma~\ref{cor:3_colours}.

\begin{lemma}
  \label{lem:3_colours}
  For all~$c>0$, there is a constant~$\tau>0$ such that, for any~$\rho>0$, there
  is a constant~$\tsigma>0$ such that for~$p=c/\sqrt n$ the random
  graph~$G=G(n,p)$ a.a.s.\ satisfies the following property.  For every proper
  $3$-colouring $E(G)=R\cup B\cup Y$ of the edges of~$G$, there are two
  colours, say~$R$ and~$B$, for which, letting
  \begin{equation*}
%    \label{eq:I_def}
    I=\Base(R)\cap\Base(B),
  \end{equation*}
  there exists a set~$U\subset V(G)$ such that
  \begin{enumerate}
  \item[(\textit{i})]$|U|\geq\tsigma n$ and
  \item[(\textit{ii})]$I[U]$ is $(\rho,\tau)$-dense.
  \end{enumerate}
\end{lemma}

Graphs that are $(\rho,\tau)$-dense for small~$\rho$ are `rich in small subgraphs'; in
particular, the following result holds~\cite{RodlRucinski95}.

\begin{lemma}
  \label{lem:dense}
  For all~$\tau>0$ there exist~$\rho$, $n_0$, and~$c_0>0$ such that every
  $(\rho,\tau)$-dense graph on~$n\geq n_0$ vertices contains at least~$c_0n^3$
  triangles.
\end{lemma}

With Lemmas~\ref{lem:3_colours} and~\ref{lem:dense} at hand, it is easy to
prove Lemma~\ref{cor:3_colours}.

\begin{proof}[Proof of Lemma~\ref{cor:3_colours}]
  Given~$c>0$, Lemma~\ref{lem:3_colours} gives us a constant~$\tau>0$.
  By Lemma~\ref{lem:dense} we obtain constants~$\rho$, $n_0$,
  and~$c_0>0$ such that any $u$-vertex $(\rho,\tau)$-dense graph with
  $u\geq n_0$ contains at least~$c_0u^3$ triangles.  We now feed this
  constant~$\rho>0$ to Lemma~\ref{lem:3_colours}, to get a
  constant~$\tsigma>0$.

  We claim that the choice of
  \begin{equation}
    \label{eq:cor_alpha_def}
    \alpha={1\over3}\tau\tsigma^2
  \end{equation}
  and
  \begin{equation}
    \label{eq:cor_beta_def}
    \beta=c_0\tsigma^3,
  \end{equation}
  will do in Lemma~\ref{cor:3_colours}.

  To prove our claim, suppose we have a proper $3$-colouring of the
  edges of~$G=G(n,p)$.  By Lemma~\ref{lem:3_colours}, a.a.s.\ there
  are two colours, say~$R$ and~$B$, and a set~$U\subset V(G)$,
  $|U|\geq\tsigma n$, for which~$I[U]=(\Base(R)\cap\Base(B))[U]$ is
  $(\rho,\tau)$-dense.  Then
  $$
  |E(I)|\geq|E(I[U])|\geq \tau{|U|\choose2}
  \geq{1\over3}\tau|U|^2\geq\({1\over3}\tau\tsigma^2\)n^2=\alpha n^2.
  $$
  Moreover, by the choice of~$\rho>0$ and~$c_0$, we deduce from
  Lemma~\ref{lem:dense} that the number of triangles in the
  $(\rho,\tau)$-dense graph~$I[U]$ is at least
  $$
  c_0|U|^3\geq c_0\tsigma^3n^3=\beta n^3.
  $$
  Lemma~\ref{cor:3_colours} is proved.
\end{proof}

Let us now briefly comment on the organization of this section.  The proof of
Lemma~\ref{lem:3_colours} fills the remainder of this section, and will
require considerable work.  This proof is based on some technical, auxiliary
results presented in Section~\ref{sec:auxiliary} and proved in
Section~\ref{sec:pf_of_auxiliary}.  The actual proof of
Lemma~\ref{lem:3_colours} is given in Section~\ref{sec:Main_Lemma}.

\subsection{Towards the proof of Lemma ~\ref{lem:3_colours}}
\label{sec:auxiliary}
In this section, we state three lemmas and prove two claims that will be
crucial in the proof of Lemma~\ref{lem:3_colours}.

Throughout this section, we assume that
$$
p={c\over\sqrt n},
$$
where~$0<c\leq1/5$ is an arbitrary constant that we fix once and for
all.  We also define once and for all the constants
\begin{equation}
  \label{eq:sigma0lambda0tau0_def}
  \sigma_0=(1/200)c^2,\qquad\lambda_0=(1/30)c^2
  \qquad\mbox{ and }\qquad\tau_0={1\over800}\lambda_0^2c^2\sigma_0.
\end{equation}

Let~$H$ be a graph.  A pair of disjoint sets $U$, $V\subset V(H)$ will be
called \textit{$(p,\lambda;H,\epsilon)$-lower semi-regular}, or
\textit{$(p,\lambda;H,\epsilon)$-semi-regular} for short, if, for all
$U'\subseteq U$, $V'\subseteq V$, with $|U'|\geq\epsilon|U|$ and
$|V'|\geq\epsilon|V|$, we have
$$
\frac{e_H(U',V')}{p|U'||V'|}\geq\lambda.
$$
Note that if $(U, V)$ is $(p,\lambda;H,\epsilon)$-semi-regular then
\begin{equation}
e_H(U,V)\ge\lambda p|U||V|.
\end{equation}
Note also that then $(U, V)$ is $(p,\lambda;H,\epsilon')$-semi-regular for any
$\epsilon'\geq\epsilon$, and $(U^*,V)$ is
$(p,\lambda;H,\epsilon/\rho)$-semi-regular for any $U^*\subseteq U$ with
$|U^*|\ge\rho |U|$.

Our first auxiliary lemma, Lemma~\ref{lem:large_sbgr}, concerns the
existence of a certain substructure in a properly
edge-coloured~$G(n,p)$.  A tripartite graph $J$ on vertex sets~$Z$, $U$,
and~$W$ with no edge between~$Z$ and~$W$ will be called an
\textit{amalgam} (of two bipartite graphs).  The amalgam guaranteed by
Lemma~\ref{lem:large_sbgr} in a properly edge-coloured~$G(n,p)$
satisfies certain properties with respect to its size, colouring and
structure (see Figure~\ref{fig:small_waist}).

\begin{figure}[ht]
%\input{small_waist2.pstex_t}
\begin{picture}(0,0)%
%\includegraphics[scale=.75]{small_waist2.pstex}%
\includegraphics[scale=.75]{small_waist2}%
\end{picture}%
%\setlength{\unitlength}{4144sp}%
\setlength{\unitlength}{3108sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(5040,2881)(1756,-3305)
\put(1756,-556){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$Z$}%
}}}
\put(1756,-3256){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$W$}%
}}}
\put(6796,-3256){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$|W|=\sigma_0n$}%
}}}
\put(6751,-556){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$|Z|=\sigma_0n$}%
}}}
\put(5851,-1906){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$|U|\geq\sigma
n$}%
}}}
\put(6076,-1546){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$(p,\lambda_0;J,\varepsilon)$-semi-regular}%
}}}
\put(6076,-2671){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$(p,\lambda_0;J,\varepsilon)$-semi-regular}%
}}}
\put(2701,-1906){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$U$}%
}}}
\put(5851,-1231){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$J_0\subseteq R$}%
}}}
\put(5851,-2356){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{rm}{$J_1\subseteq B$}%
}}}
\end{picture}

\caption{The amalgam given by Lemma~\ref{lem:large_sbgr}}
\label{fig:small_waist}
\end{figure}

\begin{lemma}
  \label{lem:large_sbgr}
   For all~$\epsilon>0$,
  there is~$\tsigma>0$ for which the following assertion holds
  a.a.s.\ for~$G=G(n,p)$.  Suppose
  \begin{equation}
    \label{eq:colouring_in_lem_large_sbgr}
    E(G)=R\cup B\cup Y
  \end{equation}
  is a proper colouring of the edges of~$G$.  Then there exist two colours,
  say~$R$ and~$B$, and a subgraph~$J$ of~$G$ which is an amalgam with vertex sets~$Z$, $U$, and~$W$, as follows:
  \begin{enumerate}
  \item[{\rm(\textit{i})}]~$|Z|=|W|=\sigma_0 n$
    and~$|U|\geq\tsigma n$,
  \item[{\rm(\textit{ii})}]we have~$E_J(Z,U)\subset R$ and~$E_J(U,W)\subset
    B$,
  \item[{\rm(\textit{iii})}]the pairs~$(Z,U)$ and~$(U,W)$ are
    $(p,\lambda_0;J,\epsilon)$-semi-regular.
  \end{enumerate}
\end{lemma}
  Basically, our second lemma
concerns the base of the subgraph~$J_0=J[Z,U]$ of an amalgam $J$ as in Lemma~\ref{lem:large_sbgr} (as well as, by symmetry, the base of $J_1=J[U,W]$).

\begin{lemma}
  \label{lem:large_base_one_colour}
  For all~$\rho>0$, there is~$\epsilon>0$ such that a.a.s.~$G=G(n,p)$ satisfies the following
  property.  For all bipartite subgraphs~$J_0$ of~$G$ with bipartition $(Z,U)$ and such that
  \begin{enumerate}
  \item[{\rm(\textit{i})}]$z=|Z|=\sigma_0n$ and~$u=|U|\geq n/\log n$, and
  \item[{\rm(\textit{ii})}]$(Z,U)$ is $(p,\lambda_0;J_0,\epsilon)$-semi-regular,
  \end{enumerate}
  the graph~$\Base(J_0)[U]$ is $(\rho,\tau_0)$-dense.
\end{lemma}

Lemma~\ref{lem:large_base_one_colour} follows immediately from the next claim.
Let $J_0^*$ be a bipartite graph with bipartition $(Z,U^*)$.  Recall that we
have the constants~$\sigma_0$, $\lambda_0$ and~$\tau_0$, defined in~\eqref{eq:sigma0lambda0tau0_def}.
Given~$\epsilon'>0$, we
shall say that $J_0^*$ is $\epsilon'$-{\it rare} if
\begin{enumerate}
\item[{\rm(\textit{i$^*$})}]$z=|Z|=\sigma_0n$ and~$u^*=|U^*|\geq n/\log n$,
\item[{\rm(\textit{ii$^*$})}]$(Z,U^*)$ is
  $(p,\lambda_0;J_0^*,\epsilon')$-semi-regular, and
\item[{\rm(\textit{iii$^*$})}]$|\Base(J_0^*)[U^*]|<\tau_0\binom{u^*}2.$
\end{enumerate}

\begin{claim}
  \label{new_claim}
  If~$\epsilon'>0$ is small enough, then a.a.s.\ $G=G(n,p)$~contains no
  $\epsilon'$-rare bipartite subgraph.
\end{claim}

To deduce Lemma \ref{lem:large_base_one_colour} from Claim \ref{new_claim}
take $\epsilon=\epsilon'\rho$.  In turn, Claim \ref{new_claim} follows easily
from a special case of Lemma~\ref{lem:bites_out_right} below.

\begin{proof}[Proof of Claim \ref{new_claim}]
  Put $F=K_{u^*}$, $\tau'=1$, and $\alpha=\lambda_0/2e$ into
  Lemma~\ref{lem:bites_out_right} obtaining the desired value of $\epsilon'$.
  We will apply the first moment method. By Lemma~\ref{lem:bites_out_right},
  the expected number of $\epsilon'$-rare bipartite subgraphs of $G(n,p)$ is
  at most
  \begin{multline*}
    \sum_{u^*}\sum_T\binom{n}{u^*}\alpha^T\binom{u^*z}{T}p^T
    \le\sum_{u^*}\sum_Tn^{u^*}\left(\frac{\alpha
        e}{\lambda_0}\right)^T\\
    <n^n2^{-\Omega(n^{3/2}/(\log n)^2)}=o(1).
  \end{multline*}
  The summation above extends over all integers $n/(\log n)^2\le u^*\le n$
  and $\lambda_0pzu^*\le T\le\binom n2$. Note that $\lambda_0pzu^*\ge
  \lambda_0\sigma_0cn^{3/2}/(\log n)^2$.
\end{proof}

As an immediate consequence of Lemmas~\ref{lem:large_sbgr}
and~\ref{lem:large_base_one_colour} we conclude that for all $\rho>0$ there
exists $\tsigma>0$ such that a.a.s.~$G=G(n,p)$ contains an amalgam~$J$ that
satisfies~(\textit{i})--(\textit{iii}) of Lemma~\ref{lem:large_sbgr} and such
that $\Base(J_0)[U]$ is $(\rho,\tau_0)$-dense.  Suppose
that~$I[U]=(\Base(R)\cap\Base(B))[U]$ is \textit{not}~$(\rho,\tau)$-dense for
some~$\tau$.  Then, because
$$
I[U]=(\Base(R)\cap\Base(B))[U]\supseteq(\Base(J_0)\cap\Base(J_1))[U],
$$
the graph $(\Base(J_0)\cap\Base(J_1))[U]$ is not $(\rho,\tau)$-dense either.
This means that there exists a set $U^*\subseteq U$, with
$u^*=|U^*|\ge\rho|U|$, such that
$$
|(\Base(J_0)\cap\Base(J_1))[U^*]|<\tau\binom{u^*}2.
$$
The subset~$U^*$ generates a subamalgam~$H$ of~$J$, which, as our next
result shows, is very unlikely to appear in ~$G(n,p)$.

Now come the details.  Let~$Z$, $U^*$, and~$W$ be three pairwise
disjoint sets of vertices.
Given $\epsilon'$ and $n$, let us call an
amalgam $H$ with tripartition $(Z,U^*,W)$
$\epsilon'$-\textit{rare} if

\begin{enumerate}
\item[{\rm(\textit{i})}]we have
\begin{gather}
  |Z|=|W|=\sigma_0n,\label{eq:ZWsizes}\\
  u^*=|U^*|\geq n/(\log n)^2,\label{eq:u*_large}\\
  \Delta(H)\le 2c\sqrt n,\label{eq:Delta_bdd}
\end{gather}
\item[{\rm(\textit{ii})}]the pairs~$(Z,U^*)$ and~$(U^*,W)$ are
  $(p,\lambda_0;H,\epsilon')$-semi-regular,
\item[{\rm(\textit{iii})}]letting~$H_0=H[Z,U^*]$ and~$H_1=H[U^*,W]$,
  $$
  |\Base(H_0)[U^*]|\geq\tau_0{|U^*|\choose2},
  $$
\end{enumerate}
and
\begin{enumerate}
\item[{\rm(\textit{iv})}]we have
  \begin{equation}
    \label{eq:cor-small_cap}
    |(\Base(H_0)\cap \Base(H_1))[U^*]|
    <\tau_0^3{|U^*|\choose2}.
  \end{equation}

\end{enumerate}
Note the symmetry of the roles of $H_0$ and $H_1$ in the above definition.
We will make use of it later in the proof.
\begin{claim}
  \label{claim:3_colours_prob}
  If~$\epsilon'>0$ is small enough, then a.a.s.\ $G=G(n,p)$~contains no
  $\epsilon'$-rare amalgam.
\end{claim}

Claim~\ref{claim:3_colours_prob} follows from Lemma~\ref{lem:bites_out_right},
a delicate result indicating that some bipartite graphs are rare.  In order to
state Lemma~\ref{lem:bites_out_right}, we need to introduce more definitions
and notation.

Let~$U^*$ and~$W$ be two disjoint sets of vertices.  Suppose~$F\subset[U^*]^2$
is a graph with vertex set~$U^*$.    Suppose now that we have a constant
 $\epsilon'>0$
and integers
$n$ and $T$.
Suppose further that
$w=|W|=\sigma_0n$, $u^*=|U^*|\geq n/(\log n)^2$, and
  $|F|=\tau'{u^*\choose2}$.
We call a bipartite graph $H$ with bipartition $(U^*,W)$ {\it $(F,\epsilon')$-rare} if
\begin{enumerate}
\item[{\rm(\textit{i})}]$|E|=T$ and $\Delta(H)\leq2c\sqrt n$,
\item[{\rm(\textit{ii})}]$(U^*,W)$ is
  $(p,\lambda_0;H,\epsilon')$-semi-regular, and
\item[{\rm(\textit{iii})}]we have  \begin{equation}
    \label{eq:cB_def_ineq}
    |F\cap \Base(H)[U^*]|<\tau_0\tau'|F|.
  \end{equation}
\end{enumerate}

Finally, let
\begin{equation}
  \label{eq:cB_bip_def}
  \cB_1=\cB_1(U^*,W;F;\tau',\epsilon';n,T)
\end{equation}
be the family of all $(F,\epsilon')$-rare, bipartite graphs~$H$.
We are now ready to state our third auxiliary lemma, the formulation of which is
based on the notation and definitions introduced above.

\begin{lemma}
  \label{lem:bites_out_right}
  Let any constants~$\tau'>0$ and~$0<\alpha\leq1$
  be given.  Then there exist constants~$\epsilon'>0$ and~$n_0$ such that,
  with the notation as above, for all~$n\geq n_0$, all $F$ as above, and all~$0\le T\le u^*w$, we
  have
  $$
  |\cB_1(U^*,W;F;\tau',\epsilon';n,T)|
  \leq\alpha^T{u^*w\choose T}.
  $$
\end{lemma}

Lemma~\ref{lem:bites_out_right} is a statement concerning the uniform space of
the \textit{bipartite graphs} with vertex classes~$U^*$ and~$W$, and $T$
edges.  Indeed, this lemma asserts that a random element of this space is
extremely unlikely to be a member of the family $\cB_1$ defined
in~\eqref{eq:cB_bip_def}, as the probability that this happens can be made
subexponentially small.

The proof of Lemma~\ref{lem:bites_out_right} is postponed to
Section~\ref{sec:proof-bites_out_right}.

\begin{proof}[Proof of Claim \ref{claim:3_colours_prob}] We first show that, for  a suitable $\epsilon'$, $\epsilon'$-rare amalgams
 really   are  rare among all
  amalgams of that size. We feed $\tau'=\tau_0$ and
  \begin{equation}
    \label{eq:alpha_def0}
    \alpha=\frac12\(\lambda_0\over e\)^{2}
  \end{equation}
  into Lemma~\ref{lem:bites_out_right}, and obtain a constant~$\epsilon'>0$. Let
  \begin{equation}
    \label{eq:cBZU*W_def}
    \cB_2=\cB_2(Z,U^*,W;\epsilon';n,T,T')
  \end{equation}
  be the family of $\epsilon'$-rare amalgams~$H$ on~$Z\cup U^*\cup W$, with $T$ edges with
  endpoints in $W$ and $T'$ edges with endpoints in $Z$.

\begin{fact}\label{B2}
For
  all~$T$ and~$T'$, we have
  \begin{equation}\label{former_L2}
    |\cB_2(Z,U^*,W;\epsilon';n,T,T')|
    \leq\alpha^T{zu^*\choose T'}{wu^*\choose T}.
  \end{equation}
\end{fact}

\begin{proof}
  For any graph $H\in\cB_2$, we let~$H_0=H[Z,U^*]$ and~$H_1=H[U^*,W]$.  To show (\ref{eq:cBZU*W_def}), we may
  count the graphs in~$\cB_2$ by estimating the number of~$H_0$ crudely  by
  \begin{equation}
    \label{eq:H_0_upbd}
    {zu^*\choose T'},
  \end{equation}
  and, for each fixed~$H_0$, estimating the number of~$H_1$ that we may `put
  together with~$H_0$' to form a graph~$H$ in~$\cB_2$.


  Let us now fix a bipartite graph~$H_0$ with bipartition $(Z,U^*)$ satisfying
  conditions~(\textit{i})--(\textit{iii}) in the definition of $\epsilon'$-rare amalgams.
  Moreover, let a subgraph
  $$
  F\subset \Base(H_0)[U^*]
  $$
  with~$|F|=\tau_0{|U^*|\choose2}$ be fixed.  If for some~$H_1$ with bipartition $(U^*,W)$ the amalgam~$H=H_0\cup H_1\in\cB_2$, then
  \begin{equation}
    \label{eq:H_1_as_in_Lemma}
    H_1\in\cB_1=\cB_1(U^*,W;F;\tau',\epsilon';n,T),
  \end{equation}
that is, $H_1$ is $(F,\epsilon')$-rare.
  Indeed, conditions~(\textit{i}) and~(\textit{ii}) in the definition of~$\cB_1$
  clearly hold for~$H_1$.  To check condition~(\textit{iii}), we observe that,
  in view of~\eqref{eq:cor-small_cap}, we have
  $$
  |F\cap \Base(H_1)[U^*]|\leq|(\Base(H_0)\cap \Base(H_1))[U^*]|
  <\tau_0^3{|U^*|\choose2} =\tau_0^2|F|.
  $$
  Therefore~\eqref{eq:cB_def_ineq} holds (with $\tau'=\tau_0$), and so does
  condition~(\textit{iii}) in the definition of~$\cB_1$.  We conclude
  that~\eqref{eq:H_1_as_in_Lemma} is true.

  To verify~\eqref{former_L2}, it now suffices to put together the bounds in~\eqref{eq:H_0_upbd} and in
  Lemma~\ref{lem:bites_out_right} (with $\tau'=\tau_0$).
\end{proof}

We now use Fact \ref{B2} to show that the random graph~$G(n,p)$ is
quite unlikely to contain $\epsilon'$-rare amalgams~$H$.

  Note that if~$H$ is an $\epsilon'$-rare amalgam with $T+T'$ edges, then,
\begin{equation}
    \label{eq:TT'_large}
    T,\;T'\geq\lambda_0 p|Z||U^*|
    =\lambda_0 p|W||U^*|
    =\lambda_0\sigma_0pnu^*,
\end{equation}
and hence, as~\eqref{eq:u*_large} holds, we have
\begin{equation}
  \label{eq:TT'_super_linear}
  T,\;T'=\Omega(n^{3/2}/\log n)\gg n\log n.
\end{equation}
Without loss of generality we may assume that $T\ge T'$.
  We are now ready to show that a.a.s.\ no $\epsilon'$-rare amalgam occurs as a subgraph
  in~$G=G(n,p)$.  Similar to the proof of Claim \ref{new_claim},
we shall use the first moment method.  The expected number
  of such subgraphs is
  \begin{equation}
    \label{eq:the_rare_expectation}
    \sum|\cB_2(Z,U^*,W;\epsilon';n,T,T')|\,p^{T+T'},
  \end{equation}
  where the sum is over all choices of~$Z$, $U^*$, $W\subset V(G)$ and over
  all choices of~$T$ and~$T'$.  We use (\ref{former_L2}),
  \eqref{eq:TT'_large},  and \eqref{eq:TT'_super_linear} to estimate~\eqref{eq:the_rare_expectation}.
  Below, we write~$\sum_{u^*}$ for the sum over~$n/\log n\leq u^*\leq n$
  and~$\sum_{T,\,T'}$ for the sum over~$T$, $T'\geq\lambda_0\sigma_0pnu^*$
  (see~\eqref{eq:TT'_large}).  The quantity in~\eqref{eq:the_rare_expectation}
  is at most
  \begin{multline*}
    \sum_{u^*}\sum_{T,\,T'}\binom{n}{u^*}\binom{n}{w}\binom{n}{z}
    \alpha^T{wu^*\choose T'}{zu^*\choose T}p^{T'+T}\\
    \leq\sum_{u^*}\sum_{T,\,T'}n^{3n}
    \alpha^T\(e\over \lambda_0\)^{2T}
    \leq n^{4n}\sum_{T}\(1\over2\)^{T}\\
    \leq n^{4n}(n^2)2^{-\Omega( n^{3/2}/\log n)}=o(1).
  \end{multline*}
  Claim~\ref{claim:3_colours_prob} follows by Markov's inequality.
\end{proof}

\subsection{Proof of Lemma~\ref{lem:3_colours}}
\label{sec:Main_Lemma}
%\begin{proof}[Proof of Lemma~\ref{lem:3_colours}]
We shall use Lemmas~\ref{lem:large_sbgr},
\ref{lem:large_base_one_colour}, and Claim~\ref{claim:3_colours_prob} to prove
Lemma~\ref{lem:3_colours}.

Let~$c>0$ be given.  A moment's thought shows that the  property
asserted a.a.s. for~$G=G(n,p)$ is increasing, and therefore we may suppose
that~$c\leq1/5$ (for details concerning this argument, for instance
see~\cite[Lemma~1.10]{janson00:_random_graph}).
We set
\begin{equation}
  \label{eq:ultimate_d_def}
  \tau=\tau_0^3,
\end{equation}
and claim that this choice for~$\tau$ will do.

To prove our claim above, let an arbitrary~$0<\rho\leq1$ be given.
We have to prove the existence of a suitable constant~$\tsigma>0$.
To this end, we first invoke Lemma~\ref{lem:large_base_one_colour}
with this~$\rho$, to
obtain a constant~$\epsilon(\rmL11)>0$.
Moreover, Claim~\ref{claim:3_colours_prob} gives us a
constant
\begin{equation}
  \label{eq:epsilon'_def}
  \epsilon'(\rmC\ref{claim:3_colours_prob})>0.
\end{equation}
We now let
\begin{equation}
  \label{eq:epsilon_def}
  \epsilon'=\min\{\epsilon(\rmL11)/\rho,
  \epsilon'(\rmC\ref{claim:3_colours_prob})\}.
\end{equation}
and, finally, invoke Lemma~\ref{lem:large_sbgr} with $\epsilon=\epsilon'\rho$
to obtain
\begin{equation}
  \label{eq:tsigma_1_def}
  \tsigma=\tsigma(\rmL10)>0.
\end{equation}
We claim that~$\tsigma$ chosen above will do in
Lemma~\ref{lem:3_colours}.  In the remainder of this proof we verify this
claim.

It follows easily from the Chernoff bound that a.a.s.
\begin{equation}
  \label{eq:Delta_G_bdd}
  \Delta(G(n,p))\leq2c\sqrt n.
\end{equation}
Let $G=G(n,p)$ satisfy the conclusions of Lemmas~\ref{lem:large_sbgr}
and~\ref{lem:large_base_one_colour} and Claim~\ref{claim:3_colours_prob} with
the above parameters, as well as~$\Delta(G)\le2c\sqrt n$. (Note that all these
properties hold a.a.s.\ for $G(n,p)$.)

Suppose that we have a colouring~$E(G)=R\cup B\cup Y$ with no monochromatic
triangles.  We shall show that~$G$ must then contain the required set~$U$.

Since~$G$ satisfies the conclusion of Lemma~\ref{lem:large_sbgr}, there is
an amalgam~$J\subset G$ as in the statement of that lemma.  We follow the
notation of Lemma~\ref{lem:large_sbgr}, so that, \textit{e.g.}, $V(J)=Z\cup
U\cup W$ (see Figure~\ref{fig:small_waist} as well).

As we have~$|U|\geq\tsigma n$, condition~(\textit{i})
in Lemma~\ref{lem:3_colours} holds.  Hence, the proof of
Lemma~\ref{lem:3_colours} will be finished if we show the following
fact.

\begin{fact}
  \label{fact:this_U_will_do}
  The graph~$I[U]$ is $(\rho,\tau)$-dense.
\end{fact}
\begin{proof}
  Our proof strategy has already been unveiled just after the
  proof of Claim~\ref{new_claim}.  Here we give
  the details.\ykcomm{added this paragraph, to apologise for the
    repetition}

  Let~$J_0=J[Z,U]$ and~$J_1=J[U,W]$.  Since~$G$ satisfies the conclusion of
  Lemma~\ref{lem:large_base_one_colour}, the graph~$\Base(J_0)[U]$ is
  $(\rho,\tau_0)$-dense.\ykcomm{changed $B(\;)$ stuff; check}

  We now claim that $(\Base(J_0)\cap\Base(J_1))[U]$ is
  $(\rho,\tau)$-dense.  Note that, then, $I[U]$~must be $(\rho,\tau)$-dense,
  because
  \begin{multline*}
    \qquad I[U]=(\Base(R)\cap\Base(B))[U]
    \supseteq(\Base(J_0)\cap\Base(J_1))[U].\qquad
  \end{multline*}
  Suppose for a contradiction that~$(\Base(J_0)\cap\Base(J_1))[U]$ is not
  $(\rho,\tau)$-dense, and let~$U^*\subset U$ be a witness to this fact, that
  is, suppose that
  \begin{equation}
    \label{eq:U^*_size}
    |U^*|\geq\rho|U|
  \end{equation}
  and
  \begin{equation}
    \label{eq:U^*_witness}
    |(\Base(J_0)\cap\Base(J_1))[U^*]|<\tau{|U^*|\choose2}.
  \end{equation}

  We let~$H$ be the subgraph of~$J$ induced by~$Z\cup U^*\cup W$.  Also,
  let~$H_0=H[Z,U^*]$ and~$H_1=H[U^*,W]$, and let~$T'=|E(H_0)|$
  and~$T=|E(H_1)|$. We claim that $H$ is an $\epsilon'$-rare amalgam.
Condition (i) of the definition of an $\epsilon'$-rare amalgam clearly holds (note that $\Delta(H)\leq\Delta(G)$).

  Since~$(Z,U)$ and~$(U,W)$ are $(p,\lambda_0;J,\epsilon)$-semi-regular, by
  the choice of~$\epsilon'$ (see~\eqref{eq:epsilon_def})
  and~\eqref{eq:U^*_size}, we have that~$(Z,U^*)$ and~$(U^*,W)$ are
  $(p,\lambda_0;H,\epsilon')$-semi-regular, so condition (ii) holds too.

  We already know that~$\Base(J_0)[U]$ is $(\rho,\tau_0)$-dense, so
  that
  \begin{equation}
    \label{eq:rho-tau-dense_cond}
    |\Base(H_0)[U^*]|=|\Base(H_0)[U^*]|\geq\tau_0{|U^*|\choose2},
  \end{equation}
which verifies condition (iii). Finally note that
  \eqref{eq:U^*_witness} yields (iv), since
  \begin{equation*}
     \label{eq:U^*_witness2}
\Base(H_0)\cap\Base(H_1))[U^*]=\Base(J_0)\cap\Base(J_1))[U^*].
  \end{equation*}



  We have reached a contradiction, for we supposed that~$G$ contains no $\epsilon'$-rare
  amalgam.  This contradiction completes the proof
  of Fact~\ref{fact:this_U_will_do}, and consequently the proof of
Lemma~\ref{lem:3_colours}.
\end{proof}


\subsubsection*{Comments on the proof of Lemma~\ref{lem:pro1}}
\label{rem:pf_of_lem_pro1}
We observed in the beginning of Section~\ref{sec:proof_of_3_colours} that we
would come close to proving Lemma~\ref{lem:pro1}.  We may now expand on this
remark a little (we shall be sketchy).

Suppose~$p=c/\sqrt n$, where~$c>0$ is an arbitrary constant, and
consider~$G=G(n,p)$.  Furthermore, suppose~$F\subset E(G)$ has cardinality at
least~$\lambda_0|E(G)|$ for some fixed~$\lambda_0>0$.  We wish to show
that~$\Base(F)$ contains~$an^3$ triangles, for some constant~$a>0$.

Recall that Lemma~\ref{lem:large_sbgr} asserts the existence of a certain
substructure in a~$G(n,p)$ (an `amalgam' of two bipartite graphs) whose edges
have been properly $3$~coloured (see Figure~\ref{fig:small_waist}).  In the
case in which we have a subset of edges~$F$ of~$G=G(n,p)$ as above, one may
prove the existence, within~$F$, of, say, the `upper half' of the amalgam in
Figure~\ref{fig:small_waist}.  In fact, using the notation introduced
immediately after the statement of Lemma~\ref{lem:large_sbgr}, one may prove
the existence of the graph~$J_0$.  (The proof is roughly speaking `contained'
in the proof of Lemma~\ref{lem:large_sbgr}.)\ykcomm{slightly changed}

With a suitable graph~$J_0$ at hand, one may apply
Lemma~\ref{lem:large_base_one_colour}, and deduce that~$\Base(F)$ contains a
$(\rho,\tau)$-dense, induced subgraph with at least~$\sigma n$ vertices,
where~$\rho$, $\tau$, and~$\sigma$ are certain positive constants.  It now
follows from Lemma~\ref{lem:dense} that~$\Base(F)$ must contain~$an^3$
triangles, for some constant~$a$, as required in Lemma~\ref{lem:pro1}.

\section{Proofs of the auxiliary lemmas}
\label{sec:pf_of_auxiliary}
Out of the three auxiliary lemmas stated in Section~\ref{sec:auxiliary}, only
two remain to be proved, namely,
Lemmas~\ref{lem:large_sbgr} and~\ref{lem:bites_out_right}.  The proofs of both
results involve regular and semi-regular pairs, and hence we shall start
with a section devoted to these concepts.

\subsection{Semi-regularity}\label{S-R}

The notion of a $(p,\lambda;H,\epsilon)$-semi-regular pair has been already
defined on page 12.  When dealing with semi-regular pairs, the following
simple observation is often useful.

\begin{lemma}
  \label{prop:degrees}
  If~$(U,W)$ is $(p,\lambda;H,\epsilon)$-semi-regular and~$U_0\subseteq U$
  satisfies $|U_0|\ge\epsilon|U|$, then more than $(1-\epsilon)|W|$ vertices
  of~$W$ have each at least $\lambda p|U_0|$ neighbours in~$U_0$.
\end{lemma}
The following powerful generalization of Lemma \ref{prop:degrees}, is, in fact, its corollary.
Recall that for $V\subseteq V(H)$, $N_H(V)=\bigcup_{v\in V}N_H(v)$ is the union of the neighbourhoods in $H$ of all vertices $v\in V$.
\begin{cor}\label{L29}
  Let~$(U,W)$ be a $(p,\lambda;H,\epsilon)$-semi-regular pair, let $d<|W|$ be
  an integer, and fix $U_0\subset U$ with $|U_0|>(\epsilon/\mu)|U|$, where
  $\mu=\exp\{-\lambda pd/2\}$. Then the  number of $d$-element subsets $W_0$ of $W$ such that
\begin{equation}\label{aaa}
|U_0\setminus N_H(W_0)|>\mu|U_0|
\end{equation}
is less than
  $$
  \epsilon^{d/2}\binom{d}{d/2}|W|^d/d!.
  $$

\end{cor}
\begin{proof}
  Let~$W_0\subset W$ be a $d$-element subset of~$W$ with a fixed ordering
  $w_1,\dots,w_d$ of its elements.  We define a sequence
  \begin{equation}
    \label{eq:decreasing_Fs}
    U_0\supseteq\dots\supseteq U_d
    =U_0\setminus\bigcup_{w\in W_0}N(H_0;w)=U_0\setminus N_H(W_0)
  \end{equation}
  of descending subsets of~$W$, putting
  \begin{equation}
    \label{eq:oneF(j)}
    U_j=U_{j-1}\setminus N(H_0;w_j)
    =U_0\setminus\bigcup_{1\leq k\leq j}N(H_0;w_k),
  \end{equation}
  for all~$1\leq j\leq d$.  Let us call the ratio
  \begin{equation}
    \label{eq:shrinking_f}
    |U_j|/|U_{j-1}|
  \end{equation}
  the \textit{shrinking factor at~$j$} ($1\leq j\leq d$).  Observe that this
  factor depends only on the sequence~$w_1,\dots,w_j$.  Observe that for a set
  $W_0$ satisfying (\ref{aaa}), at least $d/2$ shrinking factors are greater
  than $1-\lambda p$. Indeed, otherwise we would have\ykncomm{changed this
  display}
  $$
  |U_d|\leq(1-\lambda p)^{d/2}|U_0|\leq\mu|U_0|.
  $$
  Note also that for each $1\le j\le d$, we have
  $$
  U_{j-1}\ge\mu|U_0|>\epsilon|U|
  $$
  and hence, by Lemma \ref{prop:degrees} there are fewer than $\epsilon|W|$
  vertices $w\in W$ with less than $\lambda p|U_{j-1}|$ neighbours in
  $U_{j-1}$.

  Let~$\cW^\times\subset W^d=W\times\dots\times W$ be the collection of
  ordered $d$-tuples $(w_1,\dots,w_d)$ that have at least~$d/2$ indices~$j$
  with shrinking factor greater than~$1-\lambda p$. It follows that
  \begin{equation}
    \label{eq:cWtimes_upbd}
    |\cW^\times|\le\binom{d}{d/2}\epsilon^{d/2}|W|^d.
  \end{equation}
  Now let~$\cW\subset[W]^d$ be the set of $d$-element subsets $W_0$ of~$W$
  that satisfy~\eqref{aaa}.  Clearly, if~$W_0\in\cW$, then any ordered
  $d$-tuple $(w_1,\dots,w_d)$ with~$W_0=\{w_1,\dots,w_d\}$ belongs
  to~$\cW^\times$ (that is, any ordering of a member of~$\cW$ is
  in~$\cW^\times$).  This and~\eqref{eq:cWtimes_upbd} give that
  \begin{equation*}
%    \label{eq:aux1}
    d!|\cW|\leq|\cW^\times|\leq\binom{d}{d/2}\epsilon^{d/2}|W|^d,
  \end{equation*}
  which completes the proof.
\end{proof}

The reader may have observed that the concepts of $(\rho,\tau)$-denseness and
$\epsilon$-semi-regularity are related (the latter is a `bipartite version' of
the former).\ykncomm{added this paragraph} Furthermore, the reader acquainted
with the celebrated regularity lemma of Szemer\'edi~\cite{szemeredi76} has
certainly observed that the notion of $\epsilon$-semi-regularity is a weaker
form of $\epsilon$-regularity.  As it turns out, it is more convenient for us
to work with this weaker notion.

However, to be able to assert the existence of suitable semi-regular pairs in
our graphs, we shall invoke the regularity lemma, which we now recall.  Since
we are dealing with sparse graphs (that is, graphs with a subquadratic number
of edges), we shall make use of an appropriate variant.  We need to introduce
some definitions.

A graph~$H$ is called \textit{$(p;b,\beta)$-bounded} if for all pairs of
disjoint subsets $U$, $V\subset V(H)$ with $|U|$, $|V|>\beta|V(H)|$ we have
$e_H(U,V)\le bp|U||V|$.  A pair $U$, $V\subset V(H)$, $U\cap V=\emptyset$, is
called \textit{$(p;H,\epsilon)$-regular} if for all $U'\subseteq U$
and~$V'\subseteq V$, with $|U'|\geq\epsilon|U|$ and $|V'|\geq\epsilon|V|$, we
have
$$
\left|\frac{e_H(U',V')}{p|U'||V'|}-\frac{e_H(U,V)}{p|U||V|}\right|
\le\epsilon.
$$
Observe that, clearly, if a pair is $(p;H,\epsilon)$-regular, then it is
also $(p,\lambda;H,\epsilon)$-semi-regular
for~$\lambda=e_H(U,V)/p|U||V|-\epsilon$.


Let~$|V(H)|=n$.  A partition $V(H)=V_1\cup\dots\cup V_k$ is
\textit{$(p;H,\epsilon,k)$-regular} if all but at most~$\epsilon\binom k2$
pairs~$(V_i,V_j)$ are $(p;H,\epsilon)$-regular, and, for all $i=1,\dots,k$, we
have $\lfloor n/k\rfloor\le |V_i|\le\lceil n/k\rceil$.  The following sparse
version of Szemer\'edi's regularity lemma will be important in what follows
(for general discussions on this lemma, see, \textit{e.g.},
\cite{janson00:_random_graph,Kohayakawa97Szemeredi,kohayakawa02:_raac}).

\begin{lemma}
  \label{lem:sRL}
  For all~$\epsilon>0$, $b\ge1$, and all integers~$m$ and~$r\geq1$, there
  exist~$\beta>0$ and~$K\ge m$ for which the following holds.  For all~$p$ and
  all $r$-tuples of $(p;b,\beta)$-bounded graphs~$(H_1,\dots,H_r)$, with all
  the~$H_i$ on the same vertex set~$V$ with~$|V|\geq m$, there exists a
  partition $V=V_1\cup\dots\cup V_k$ of~$V$ with $m\le k\le K$ that is
  $(p;H_i,\epsilon,k)$-regular for all~$1\leq i\leq r$.
\end{lemma}





\subsection{Proof of Lemma~\ref{lem:large_sbgr}}
\label{sec:proof-large_sbgr}
We start with two basic facts.
\begin{fact}
  \label{lem:bdd_min_deg}
  Let~$G$ be a graph on~$k\geq1$ vertices and with at
  least~$\gamma{k\choose2}$ edges, where~$0<\gamma\leq1$.  Then the number of
  vertices of degree at least~$\gamma k/2$ in~$G$ is at least~$\gamma
  k/2$.\qed
\end{fact}

\begin{fact}
  \label{lem:proof-2-colours}
  Suppose~$k\geq1$ and\ykcomm{changed colour $T$ to $S$}
  \begin{equation}
    \label{eq:colouring}
    E(K_k)=R\cup B\cup Y\cup S
  \end{equation}
  is a colouring of the edges of the complete graph~$K_k$ with colours red,
  blue, yellow, and sienna, where
  $$
  |R|,\;|B|\geq\gamma{k\choose2}
  $$
  and
  \begin{equation}
    \label{eq:sienna_small}
    |S|\leq{1\over8}\gamma^2{k\choose2}.
  \end{equation}
  Then there is a vertex~$x$ in~$K_k$ and distinct colours~$C_1$,
  $C_2\in\{R,B,Y\}$ such that~$x$ is incident to at least~$\gamma k/8$
  edges of colour~$C_1$ and at least~$\gamma k/8$ edges of colour~$C_2$.
\end{fact}
\begin{proof}
  For a colour~$C$ and vertex~$x$, let~$d(C,x)$ be the number of edges of
  colour~$C$ incident to~$x$ in colouring~\eqref{eq:colouring}.  For~$C=R$
  and~$B$, let
  \begin{equation}
    \label{eq:U_C_def}
    U_C=\left\{u\in V(K_k)\:d(C,x)\geq{1\over2}\gamma k\right\}.
  \end{equation}
  By Fact~\ref{lem:bdd_min_deg}, we have~$|U_R|$, $|U_B|\geq\gamma
  k/2$.  Clearly, we are done if~$U_R\cap U_B\neq\emptyset$.
  Hence we suppose that~$U_R\cap U_B=\emptyset$.  Consider the~$|U_R||U_B|$
  edges in~$E(U_R,U_B)=E_{K_k}(U_R,U_B)$.\ykcomm{added $=E_{K_k}(U_R,U_B)$}
  There is a colour~$C\in\{R,B,Y\}$ for which we have\ykncomm{changed $T$ to
  $S$, twice}
  $$
  |E(U_R,U_B)\cap C|\geq{1\over3}\(|U_R||U_B|-|S|\).
  $$
  Without loss of generality, we may assume that~$C\neq R$.  By averaging, we
  may deduce that there is a vertex~$x\in U_R$ for which we have
  \begin{multline*}
  d(C,x)\geq{|E(U_R,U_B)\cap C|\over|U_R|}
  \geq{1\over3}\(|U_B|-{|S|\over|U_R|}\)\\
  \geq{1\over3}\({1\over2}\gamma k-{(1/16)\gamma^2k^2\over\gamma k/2}\)
  ={1\over8}\gamma k,
  \end{multline*}
  and we are again done: $x$~is incident to at least~$\gamma k/2\geq\gamma
  k/8$ edges of colour~$R$ and to at least~$\gamma k/8$ edges of colour~$C\neq
  R$.
\end{proof}

We are now ready to prove Lemma~\ref{lem:large_sbgr}.

\begin{proof}[Proof of Lemma~\ref{lem:large_sbgr}]
  Let~$\epsilon>0$ be given.  Since the smaller~$\epsilon$ is, the stronger is
  the conclusion in Lemma~\ref{lem:large_sbgr}, we may suppose that
  \begin{equation}
    \label{eq:epsilon_assumption}
    \epsilon\leq{1\over30}.
  \end{equation}
  Put
  \begin{equation}
    \label{eq:delta_lambda_def}
    \delta=\min\left\{\epsilon^2,{1\over10^2}\lambda_0,
      {1\over2\times10^4}c^4\right\}
    \quad\text{and}\quad
    m={16\over3\lambda_0^2}.
  \end{equation}
  Let
  \begin{equation}
    \label{eq:K_beta_def}
    \beta=\beta(\delta,m)
    \quad\text{and}\quad
    K=K(\delta,m)
  \end{equation}
  be the constants given by Lemma~\ref{lem:sRL}, for the
  constants~$\epsilon=\delta$, $b=2$, $m$, and~$r=3$ as above.  We now let
  \begin{equation}
    \label{eq:sigma_1*_def}
    \tsigma={1\over K(\delta,m)},
  \end{equation}
  and claim that this choice for~$\tsigma$ will do.  We now proceed to prove
  this claim.  Thus, let the graph~$G$ and the edge-colouring~$E(G)=R\cup
  B\cup Y$ be as in the statement of Lemma~\ref{lem:large_sbgr}.

  The expected number of triangles in~$G$ is
  $(1/6+o(1))(np)^3=(1/6+o(1))c^3n^{3/2}$.  Also,  the expected
  number of edges~$e=\{a,b\}$ together with two further vertices~$x$ and~$y$
  ($x\neq y$) with~$x$, $y\in N(G;a)\cap N(G;b)$ (that is, the number of
  diamonds) is
  $$
  {n\choose2}{n-2\choose2}p^5\sim\({1\over4}+o(1)\)c^5n^{3/2}.
  $$
  Standard variance calculations, combined with Chebyshev's inequality,
  show that both quantities above are concentrated around their means,
  \textit{i.e.}, a.a.s.\ the number of triangles is $(1/6+o(1))c^3n^{3/2}$,
  and the number of diamonds is a.a.s.\ $(1/4+o(1))c^5n^{3/2}$.  Therefore,
  the number of triangles in~$G$ that are `solitary', that is, that share no
  edge with any other triangle,\ykcomm{changed $2/13$ to $1/7$} is a.a.s.\ 
  $$
  {1\over6}c^3n^{3/2}-{1\over4}c^5n^{3/2}\geq{1\over7}c^3n^{3/2},
  $$
  where we used that~$c\leq1/5$.  We may hence suppose that~$G$ contains at
  least~$c^3n^{3/2}/7$ solitary triangles.

  By adjusting the notation, we may suppose that
  $$
  |R|\geq|B|\geq|Y|.
  $$
  Since we are supposing that the
  colouring~\eqref{eq:colouring_in_lem_large_sbgr} contains no monochromatic
  triangle, we may deduce that~$|B\cup Y|\geq c^3n^{3/2}/7$; indeed, each
  solitary triangle must contain either a blue edge or a yellow edge, for
  otherwise it would be entirely red.  In particular, we have
  \begin{equation}
    \label{eq:R_B_large}
    |R|,\;|B|\geq{1\over14}c^3n^{3/2}.
  \end{equation}

  By Chernoff's inequality, we may also suppose that, for each pair $U$,
  $W\subset V(G)$ with $U\cap W=\emptyset$ and~$|U|$, $|W|\geq n/\log n$,
  we have
  \begin{equation}
    \label{eq:density_concentration_pair}
    {1\over2}|U||W|p\leq e_G(U,W)=|E_G(U,W)|\leq2|U||W|p,
  \end{equation}
  and
  \begin{equation}
    \label{eq:density_concentration_set}
    e_G(U)=|E(G[U])|\le |U|^2p.
  \end{equation}
 Note that it follows from~\eqref{eq:density_concentration_pair} that~$G$ is
  a.a.s.\ $(p;2,\beta)$-bounded for all~$\beta>0$.

  Let us now apply Lemma~\ref{lem:sRL} to obtain a partition
  $V(G)=V_1\cup\dots\cup V_k$ of~$V(G)$ with $m\le k\le K$ that is
  $(p;F,\delta,k)$-regular for~$F=R$, $F=B$, and~$F=Y$.  We now state and
  prove a claim that will be used in what follows.

  \begin{claim}
    \label{claim:large_dens_after_reg}
    Suppose~$F\subset E(G)$ is a subset of edges of~$G=G(n,p)$,
    with~$|F|\geq\lambda_0 cn^{3/2}$.  Let $V_1,\dots,V_k$ be a
    $(p;F,\delta,k)$-regular partition of~$V(G)$, where~$m\leq k\leq K$.
    Suppose for simplicity that~$|V_1|=\dots=|V_k|$.  Let~$\Phi$ be the set of
    pairs~$\{i,j\}$ $(1\leq i<j\leq k)$ for which~$(V_i,V_j)$ is
    $(p;F,\delta)$-regular and
    \begin{equation}
      \label{eq:large_dens}
      e_F(V_i,V_j)\geq{1\over2}\lambda_0 p\(n\over k\)^2.
    \end{equation}
    Then
    \begin{equation}
      \label{eq:Phi_large}
      |\Phi|\geq{5\over8}\lambda_0{k\choose2}.
    \end{equation}
  \end{claim}
  \begin{proof}
    Let~$\ell=x{k\choose2}=|\Phi|$ and recall that we are assuming
    that~$|V_i|=n/k$ ($1\leq i\leq k$).  Using that~$G$
    satisfies~\eqref{eq:density_concentration_pair}
    and~\eqref{eq:density_concentration_set} for all `large'~$U$ and~$W\subset
    V(G)$, we deduce that
    $$
    \lambda_0 cn^{3/2}\le|F|
    \le2\ell\(n\over k\)^2p
    +\(\binom k2-\ell\){\lambda_0 p\over2}\(n\over k\)^2
    +k\(n\over k\)^2p,
    $$
    and so
    $$
    \lambda_0\le x+{1\over4}(1-x)\lambda_0+{1\over k}.
    $$
    Solving the last inequality for~$x$, we obtain~$x\ge3\lambda_0/4$,
    because $1/k\le1/m=3\lambda_0^2/16$.  Hence, at least
    $$
    {3\over4}\lambda_0\binom k2-\delta\binom k2
    \ge{5\over8}\lambda_0\binom k2
    $$
    pairs $(V_i,V_j)$ are $(p;F,\delta)$-regular, each
    satisfying~\eqref{eq:large_dens}; that is, the set~$\Phi$
    satisfies~\eqref{eq:Phi_large}, as required.
  \end{proof}

  For~$F=R$, $B$, and~$Y$, let~$\Phi_F$ be the set of pairs $\{i,j\}$ ($1\leq
  i<j\leq k$) such that~$(V_i,V_j)$ is $(p;F,\delta)$-regular and
  \begin{equation}
    \label{eq:C_large_dens}
    e_F(V_i,V_j)\geq{1\over2}\({1\over14}c^2\)p\(n\over k\)^2
    ={1\over28}c^2p\(n\over k\)^2.
  \end{equation}
  We apply Claim~\ref{claim:large_dens_after_reg} with~$F=R$ and~$B$
  and~$\lambda_0=c^2/14$ (see~\eqref{eq:R_B_large}).  That claim tells us that
  \begin{equation}
    \label{eq:Phi_C_large}
    |\Phi_R|,\; |\Phi_B|\geq{1\over25}c^2{k\choose2}.
  \end{equation}
  Since
  $$
  3\times{1\over28}c^2p\(n\over k\)^2\leq{1\over2}p\(n\over k\)^2,
  $$
  the fact that~\eqref{eq:density_concentration_pair} holds for all
  `large'~$U$ and~$W\subset V(G)$ implies that if a pair~$\{i,j\}$ ($1\leq
  i<j\leq k$) is not a member of~$\Phi_R\cup\Phi_B\cup\Phi_Y$,
  then~$(V_i,V_j)$ is \textit{not} $(p;F,\delta)$-regular for
  some~$F\in\{R,B,Y\}$.  Put
  $$
  \Phi_S=[k]^2\setminus(\Phi_R\cup\Phi_B\cup\Phi_Y).
  $$
  The observations above, the fact that~$V_1,\dots,V_k$ is a
  $(p;F,\delta,k)$-regular partition of~$V(G)$ for~$F\in\{R,B,Y\}$, and our
  choice of~$\delta$ (see~\eqref{eq:delta_lambda_def}) imply that
  \begin{equation}
    \label{eq:Phi_S_small}
    |\Phi_S|\leq3\delta{k\choose2}
    \leq{3\over2\times10^4}c^4{k\choose2}
    <{1\over8}\({1\over25}c^2\)^2{k\choose2}.
%   ={1\over8}\gamma^2{k\choose2}.
  \end{equation}
  We now apply Fact~\ref{lem:proof-2-colours} to the following colouring of
  the edges of the complete graph~$K_k$ on~$[k]=\{1,\dots,k\}$:
  $$
  E(K_k)=\Phi_R\cup\Phi_B\cup\Phi_Y\cup\Phi_S.
  $$
  In view of~\eqref{eq:Phi_C_large} and~\eqref{eq:Phi_S_small}, we may
  apply Fact~\ref{lem:proof-2-colours} with~$\gamma=c^2/25$.  We then
  obtain~$i_0\in[k]=V(K_k)$ and two disjoint sets~$\Gamma_F'\subset[k]$ ($F=R$
  and~$B$, say) with
  \begin{equation}
    \label{eq:J_C_large}
    |\Gamma_F'|\geq{1\over8}\({1\over25}c^2\)k={1\over200}c^2k,
  \end{equation}
  such that, for all~$j\in \Gamma_F'$, we have that
  \begin{equation}
    \label{eq:used_to_be_i}
    (V_{i_0},V_j)\text{ is $(p;F,\delta)$-regular}
  \end{equation}
  and
  \begin{equation}
    \label{eq:used_to_be_ii}
    e_F(V_{i_0},V_j)\geq{1\over28}c^2p\(n\over k\)^2.
  \end{equation}
  We let~$\Gamma_F\subset \Gamma_F'$ ($F=R$ and~$B$) be an arbitrary subset of~$\Gamma_F'$
  with~$|\Gamma_F|=(c^2/200)k$.  Moreover, let
  $$
  U=V_{i_0},
  \quad Z=\bigcup_{j\in \Gamma_R}V_j,
  \quad\text{and}\quad W=\bigcup_{j\in \Gamma_B}V_j,
  $$
  and let
  \begin{equation}
    \label{eq:J_def}
    J=R[Z,U]\cup B[U,W].
  \end{equation}
  \begin{claim}
    \label{claim:J_will_do}
    We claim that~$J$, $Z$, $U$, and~$W$ satisfy~{\rm(\textit{i})},
    {\rm(\textit{ii})}, and~{\rm(\textit{iii})} of Lemma~\ref{lem:large_sbgr}.
  \end{claim}
  \begin{proof}
    We start by noticing that
    $$
    |Z|=|W|={1\over200}c^2k\times{n\over k}={1\over200}c^2n=\sigma_0n.
    $$
    Moreover,
    $$
    |U|={n\over k}\geq{n\over K(\delta,m)}=\tsigma n.
    $$
    Property~(\textit{ii}) asserted in Lemma~\ref{lem:large_sbgr} is clear
    from the definition of~$J$ (see~\eqref{eq:J_def}).  We are now left with
    proving~(\textit{iii}), that is, that $(Z,U)$ and~$(U,W)$ are
    $(p,\lambda_0;J,\epsilon)$-semi-regular.  We deal with~$(Z,U)$, as the
    other case is analogous.

    Let~$U'\subset U$ and~$Z'\subset Z$ be such that~$|U'|\geq\epsilon|U|$
    and~$|Z'|\geq\epsilon|Z|$.  We have to show that
    \begin{equation}
      \label{eq:semi-reg}
      {e_J(U',Z')\over p|U'||Z'|}\geq{1\over30}c^2=\lambda_0.
    \end{equation}
    Put~$Z_j'=Z'\cap V_j$ ($j\in \Gamma_R$).  Clearly, we have
    $e_J(U',Z')=\sum_{j\in \Gamma_R}e_J(U',Z_j')$.  Therefore, we have
    \begin{multline}
      \label{eq:deduce-semi-reg}
      \qquad{e_J(U',Z')\over p|U'||Z'|}
      =\sum_{j\in \Gamma_R}{e_J(U',Z_j')\over p|U'||Z_j'|}
      \times{|U'||Z_j'|\over|U'||Z'|}\\
      =\Bigg(\sum_{j\in \Gamma_R'}+\sum_{j\in \Gamma_R''}\Bigg)
      {e_J(U',Z_j')\over p|U'||Z_j'|}\times{|Z_j'|\over|Z'|},\qquad
    \end{multline}
    where~$\Gamma_R'=\{j\in \Gamma_R\:|Z_j'|/|V_j|<\delta\}$, and~$\Gamma_R''=\Gamma_R\setminus
    \Gamma_R'$.  We now claim that
    \begin{equation}
      \label{eq:J_R''_large_eight}
      \sum_{j\in \Gamma_R''}{|Z_j'|\over|Z'|}\geq1-\epsilon.
    \end{equation}
    Indeed,
    \begin{equation*}
      \sum_{j\in \Gamma_R'}|Z_j'|
      \leq\delta\sum_{j\in \Gamma_R'}|V_j|\leq\delta|Z|.
    \end{equation*}
    Moreover, $|Z'|\geq\epsilon|Z|$, and hence
    \begin{equation}
      \label{eq:2}
      \sum_{j\in
        \Gamma_R'}|Z_j'|\leq\delta\({1\over\epsilon}|Z'|\)\leq\epsilon|Z'|,
    \end{equation}
    as~$\delta\leq\epsilon^2$ (see~\eqref{eq:delta_lambda_def}).  It follows
    from~\eqref{eq:2} that~\eqref{eq:J_R''_large_eight} does indeed hold.

    We now go back to~\eqref{eq:deduce-semi-reg}.  Clearly, the right-hand
    side of~\eqref{eq:deduce-semi-reg} is, by~\eqref{eq:used_to_be_i},
    \eqref{eq:used_to_be_ii}, and~\eqref{eq:J_R''_large_eight}, at least
    \begin{multline*}
      \sum_{j\in \Gamma_R''}{e_J(U',Z_j')\over p|U'||Z_j'|}
      \times{|Z_j'|\over|Z'|}
      \geq\({1\over28}c^2-\delta\)\sum_{j\in \Gamma_R''}{|Z_j'|\over|Z'|}\\
      \geq\({1\over28}c^2-\delta\)(1-\epsilon)\geq{1\over30}c^2
      =\lambda_0
    \end{multline*}
    We have thus shown that~\eqref{eq:semi-reg} does indeed hold, and so   $(Z,U)$ is
    $(p,\lambda_0;J,\epsilon)$-semi-regular. This concludes the proof of
    Claim~\ref{claim:J_will_do}.
  \end{proof}
  Claim~\ref{claim:J_will_do} completes the proof of
  Lemma~\ref{lem:large_sbgr}.
\end{proof}



\subsection{Proof of Lemma~\ref{lem:bites_out_right}}
\label{sec:proof-bites_out_right}
  The basic underlying idea
in this proof comes from~\cite[Lemma~11]{KLRap3} (see
also~\cite[Lemma~8.30]{janson00:_random_graph}).

We start by letting arbitrary positive constants
$\tau'$, and~$\alpha$ be
given.
 To prove Lemma~\ref{lem:bites_out_right}, we need to define an appropriate
constant~$\epsilon'>0$.  Put
\begin{equation}
  \label{eq:epsilon''_def}
  \epsilon'=\min\left\{{1\over16}(\alpha/3)^{96/\lambda_0\tau'\sigma_0},
    {1\over4}\tau'\exp\{-\lambda_0c^2/3\}\right\}.
\end{equation}
We claim that this choice for~$\epsilon'$ will do.

Recall that we wish to estimate the number of bipartite graphs~$H$ with bipartition $(U^*,W)$, where $|W|=w=\sigma_0 n$ and $|U^*|=u^*\ge n/(\log n)^2$,
belonging to the family
$$
\cB_1=\cB_1(U^*,W;F;\tau',\epsilon';n,T),$$ where
\begin{equation}\label{F}
F\subseteq[U^*]^2,\qquad |F|=\tau'\binom{u^*}2.
\end{equation}
 In order to obtain this estimate, let us make the following observation
about the graphs~$H\in\cB_1$.

\begin{lemma}
  \label{lem:split_half}
  Suppose~$H\in\cB_1$.  Then~$H$ is a union of two edge-disjoint
  subgraphs~$H'$ and~$H''$ with $|E(H')|=|E(H'')|=T/2$, and such that
  the pair~$(U^*,W)$ is both,
  $(p,\lambda_0/3;H',\epsilon')$-semi-regular and $(p,\lambda_0/3;H'',\epsilon')$-semi-regular.
\end{lemma}
\begin{proof}
  It suffices to use the `probabilistic method', taking a random partition.
  The result follows from standard exponential estimates for the tail of the
  hypergeometric distribution.  We omit the details.
\end{proof}

For each graph~$H\in\cB_1$, we fix a decomposition  $H=H'\cup H''$.
By Lemma~\ref{lem:bdd_min_deg}, there exists a
set~$U^{**}\subset U^*$ such that
\begin{equation}
  \label{eq:u^**_def}
u^{**}=|U^{**}|\geq\tau' u^*/2
\end{equation}
and for all
$v\in U^{**}$ we have $\deg_F(v)\ge\tau' u^*/2$.
We now need to fix some notation.  Let
  $$U^{**}=\{v_i\:1\leq i\leq u^{**}=|U^{**}|\}.$$
and let
\begin{equation}
  \label{eq:F_i_def}
  F_i=N(F;v_i),\qquad W^{(i)}=N(H'';v_i)
\end{equation}
be the neighbourhoods of~$v_i$ in the graph~$F$ and $H''$, respectively.
Because of our choice of~$U^{**}$, we have
\begin{equation}
  \label{eq:f_i_def}
  |F_i|=\deg_F(v_i)\geq {1\over2}\tau'u^*
\end{equation}
for all~$1\leq i\leq u^{**}$.

Let $d_i=|W^{(i)}|$. Then, by the
$(p,\lambda_0/3;H'',\epsilon')$-semi-regularity of $(U^*,W)$, it follows from Lemma \ref{prop:degrees} that for
at least $u^{**}-\epsilon' u^*>u^{**}/2$ indices $i$, we have
$d_i\ge(\lambda_0/3)p |W|$ (note that $\epsilon'<\tau'/4$).  Thus, we may suppose that
\begin{equation}
  \label{eq:d_i_large}
  {1\over3}\lambda_0 p|W|\leq d_i\leq2c\sqrt n
  \text{\quad for all\quad $1\leq i\leq u^{**}/2$}
\end{equation}
(recall that~$\Delta(H)\leq2c\sqrt n$).  It will be convenient to set
\begin{equation}
  \label{eq:W(i)_def}
  W^{(i)}=\{w_1^{(i)},\dots,w_{d_i}^{(i)}\}
\end{equation}
for all~$1\leq i\leq u^{**}/2$.

Let
\begin{gather}
  \mu_0=\exp\{-\lambda_0^2c^2\sigma_0/18\}\label{eq:beta_0_def}.
\end{gather}
We shall say that~$v_i$ ($1\leq i\leq
u^{**}/2$) is \textit{bad} if
$$
|F_i\setminus N(H';W^{(i)})|\ge\mu_0|F_i|.
$$
We claim that more than $u^{**}/4$ vertices are bad.
 Suppose for a contradiction that the number of vertices~$v_i$ ($1\leq i\leq
  u^{**}/2$) that are  {\it not} bad is at least~$u^{**}/4$.
  Let~$v_i$ be one of them. Clearly, the number of edges of $F\cap
  \Base(H)[U^*]$ adjacent to $v_i$ is precisely $|F_i\cap N(H';W^{(i)})|$ (this is the set of $H'$-neighbours of the $H''$-neighbours of $v_i$ which are also $F$-neighbours of $v_i$).
  Since $v_i$ is not bad, we have
  \begin{equation}
    \label{eq:per_good_vx}
     |F_i\cap N(H';W^{(i)})|\ge(1-\mu_0)|F_i|
    \geq{1\over50}\lambda_0^2c^2\sigma_0|F_i|,
  \end{equation}
  where we used that~$x=(1/18)\lambda_0^2c^2\sigma_0\leq1/2$, and hence
  $1-e^{-x}\geq x/2$, say.  However, this means that~$v_i$ contributes
  to~$F\cap \Base(H)[U^*]$ at least as many pairs as in~\eqref{eq:per_good_vx}
  (with some pairs counted twice, when all $v_i$ are considered).
  Consequently, by (\ref{eq:sigma0lambda0tau0_def}), (\ref{F}),
  (\ref{eq:u^**_def}) and (\ref{eq:f_i_def})
  \begin{multline}
    \label{eq:global_lwbd}
    |F\cap  \Base(H)[U^*]|
    \geq{1\over4}u^{**}\times{1\over2}\({1\over50}\lambda_0^2c^2\sigma_0{1\over2}\tau'
    u^*\)\\
    \geq\tau_0(\tau')^2{u^*\choose2}
    =\tau_0\tau'|F|,
  \end{multline}
   which is in contradiction to the fact
  that~$H\in\cB_1$ (see~\eqref{eq:cB_def_ineq}).

\begin{proof}[Completion of the proof of Lemma~\ref{lem:bites_out_right}]
  Suppose~$H\in\cB_1$ is given.  In view of
  Lemma~\ref{lem:split_half}, we may decompose~$H$ as a union~$H'\cup H''$,
  so that $|E(H')|=|E(H'')|=T/2$ and ~$(U^*,W)$ is
  both, $(p,\lambda_0/3;H',\epsilon')$-semi-regular, and \newline$(p,\lambda_0/3;H'',\epsilon')$-semi-regular.

  We estimate the cardinality
  of
  $$
  \cB_1=\cB_1(U^*,W;F;\sigma_0,\lambda_0,\tau',\epsilon';n,T)
  $$
  as follows.  We `generate' the members~$H\in\cB_1$ in two rounds: first
  $H'$, then~$H''$.  We do not require that~$H'$ and~$H''$ above be
  disjoint. Since we are after an upper bound for~$|\cB_1|$, this is
  justified.

  The number of choices of $H'$ is bounded crudely by $\binom{wu^*}{T/2}$.  With fixed $H'$, for every $H''$ such that $H'\cup
  H''\in\cB_1$, there exist $u^{**}/4$ bad vertices $v_i\in U^*$ with
  $d_i=|N(H';v_i)|\ge(\lambda_0/3)pw$. For each one of them we apply Corollary \ref{L29} to $H'$ with $d=d_i$, $U_0=F_i$, $W_0=W^{(i)}$, $\epsilon=\epsilon'$, $\lambda=\lambda_0/3$ and $\mu=\exp\{-\lambda_0pd/6\}$.

We have $|F_i\setminus
  N(H';W^{(i)})|>\mu_0|F_i|\ge\mu|F_i|$, and thus (\ref{aaa}) holds.  We also have
  $$
  |F_i|
  \ge\tau'u^*/2>\epsilon'\exp\{\lambda_0c^2/3\}u^*
  \ge(\epsilon'/\mu)u^*.
  $$
  Hence, by Corollary \ref{L29} the number of choices of the
  neighbourhood $N(H'';v_i)$ is at most
  \begin{equation}\label{bound}
  (\epsilon')^{d/2}\binom{d}{d/2}w^d/d!<(\epsilon')^{d/2}2^d\binom wd.
  \end{equation}
  Thus, an upper bound on the number of choices of~$H''$ may be obtained by
  bounding first the number of choices of the $u^{**}/4$ bad vertices by
  $2^{u^*}$, and then summing the products
  \begin{equation}
    \label{eq:valid_choices_upbd}
    (2\sqrt{\epsilon'})^D
    \prod\left\{{w\choose d(v)}\:v\in U^{*}\right\}
  \end{equation}
  over all degree sequences~$\bfd=\{d(v)\:v\in U^{*}\}$,
  where~$D=(1/12)\lambda_0 pu^{**}w$ is a lower bound on the sum of the
  degrees of all bad vertices (cf.~\eqref{eq:d_i_large}).  Indeed, with a
  fixed set of bad vertices $U^{***}$, and fixed degree sequence $\bfd$, by
  (\ref{bound}) there are at most
  $$\prod_{v\in U^{***}}(\epsilon')^{d(v)/2}2^{d(v)}\binom {w}{d(v)}
  \times\prod_{v\in U^{*}\setminus U^{***}}\binom {w}{d(v)}$$
  choices of the
  neighbourhoods which together create $H''$.  To estimate the quantity
  in~\eqref{eq:valid_choices_upbd}, we observe that,
  because~$\Delta(H)\leq2c\sqrt n$, we have~$T\leq2c\sqrt n|U^*|=2cu^*\sqrt
  n$.  Moreover, we recall that $u^{**}\geq\tau' u^*/2$, $p=c/\sqrt n$,
  and~$w=\sigma_0n$, and hence we have
  \begin{equation*}
    {D\over T}\geq{(1/12)\lambda_0 pu^{**}w\over2c\sqrt nu^*}
    \geq{1\over48}\lambda_0\tau'\sigma_0.
  \end{equation*}
  Therefore, given $H'$, there are at most
  \begin{equation}
    \label{eq:valid_choices_upbd_tmp}
    2^{u^{*}}(2\sqrt{\epsilon'})^{(\lambda_0\tau'\sigma_0/48)T}
    \prod\left\{{w\choose d(v)}\:v\in U^{*}\right\}
  \end{equation}
  choices for~$H''$.  We now sum~\eqref{eq:valid_choices_upbd_tmp} over all
  choices of~$\bfd=\{d(v)\:v\in U^{*}\}$.  Recalling that~$\bfd$ is a
  partition of~$T/2$, and that 
  \begin{equation}
    \label{eq:valid_choices_upbd_aux2}
    T\geq\lambda_0 pu^*w=\lambda_0 c\sigma_0u^*\sqrt n\gg u^*
  \end{equation}
  (cf.~\eqref{eq:TT'_large} and~\eqref{eq:TT'_super_linear}), we see that this
  sum is at most
  \begin{equation}
    \label{eq:valid_choices_upbd_aux3}
    (4\sqrt{\epsilon'})^{(\lambda_0\tau'\sigma_0/48)T}{wu^*\choose T/2}.
  \end{equation}
  To obtain the desired bound on $\cB_1$ we have to multiply the above by
  $\binom{wu^*}{T/2}$, the number of choices for $H'$.  As, crudely,
  $$
  \binom{wu^*}{T/2}^2<3^T\binom{wu^*}T,
  $$
  Lemma~\ref{lem:bites_out_right} is proved by our choice of $\epsilon'$.
\end{proof}

\section{Concluding remarks}
\label{sec:conclude}
We close by mentioning a few remarks and open problems.

\subsubsection*{The online game for more colours}
We hope to address the online game when the Painter has~$r>2$ colours in the
near future.\ykcomm{wasn't clear to me---I kept this about online games with
  more colours}

\subsubsection*{General graphs}
It would be most interesting to generalize our results for general graphs~$H$,
that is, for avoidance games in which the Painter has to avoid monochromatic
copies of a given graph~$H$.  However, our methods are deeply based on the
simple structure of the triangles and hence a completely new approach may be
needed.

Our results above suggest that, in the two-round game for arbitrary
graphs~$H$, the first interesting case is the one in which~$r=2$ and~$N_0$ is
around the threshold for the corresponding Ramsey property, that is,
$N_0=\Theta(n^{2-1/d_2(H)})$,
where~$d_2(H)=\max\{(|E(F)|-1)/(|V(F)|-2)\:F\subseteq H,\;|V(F)|>2\}$
(see~\cite{RodlRucinski95}).

\subsubsection*{Deterministic games}
In the deterministic version of our online game, say for~$r=2$ and~$H=K_k$,
the edges are generated not randomly, but by an adversary.  Hence, this is a
two-person game with the payoff to the Painter equal to the number of coloured
edges until she is forced to form a monochromatic clique~$K_k$.

Define the \textit{online Ramsey number~$\bar R(k)$} as the value of this
game.  The question is whether it is true that~$\bar R(k)=o(R(k)^2)$ as
$k\to\infty$, where $R(k)$ is the classical Ramsey number.  Some preliminary
results in this direction have been proved by Kurek and
Ruci\'nski~\cite{kurek02:_ramsey}. In particular, $\bar R(3)=8$ and $\bar
R(k,l)=o(R(k,l)^2)$ as $k\to\infty$ while $l\ge3$ is fixed, where $R(k,l)$ and
$\bar R(k,l)$ are the corresponding off-diagonal numbers.

Finally, we mention that other games inspired by Ramsey's theorem have been
investigated in several forms.  The reader is referred to, for instance,
Beck~\cite{beck81:_waerd_ramsey,beck85:_random,beck94:_deter,beck96:_found},
Beck and Csirmaz~\cite{beck82:_variat}, Erd\H os and Selfridge~\cite{erdos73},
and Seress~\cite{seress92}.

%\bibliographystyle{amsplain}
%\bibliography{refs}

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{beck82:_variat}
J.~Beck and L.~Csirmaz, \emph{Variations on a game}, J. Combin. Theory Ser. A
  \textbf{33} (1982), no.~3, 297--315. \MR{84a:90092}

\bibitem{beck81:_waerd_ramsey}
J{\'o}zsef Beck, \emph{van der {W}aerden and {R}amsey type games},
  Combinatorica \textbf{1} (1981), no.~2, 103--116. \MR{84a:90093}

\bibitem{beck85:_random}
\bysame, \emph{Random graphs and positional games on the complete graph},
  Random graphs '83 (Pozna\'n, 1983), North-Holland, Amsterdam, 1985,
  pp.~7--13. \MR{87j:05130}

\bibitem{beck94:_deter}
\bysame, \emph{Deterministic graph games and a probabilistic intuition},
  Combin. Probab. Comput. \textbf{3} (1994), no.~1, 13--26. \MR{95h:90191}

\bibitem{beck96:_found}
\bysame, \emph{Foundations of positional games}, Proceedings of the Seventh
  International Conference on Random Structures and Algorithms (Atlanta, GA,
  1995), vol.~9, 1996, pp.~15--47. \MR{99h:90128}

\bibitem{BBf}
B{\'e}la Bollob{\'a}s, \emph{Random graphs}, Academic Press Inc. [Harcourt
  Brace Jovanovich Publishers], London, 1985. \MR{87f:05152}

\bibitem{erdos73}
P.~Erd{\H{o}}s and J.~L. Selfridge, \emph{On a combinatorial game}, J.
  Combinatorial Theory Ser. A \textbf{14} (1973), 298--301. \MR{48 \#5655}

\bibitem{frankl86:_large_k}
P.~Frankl and V.~R{\"o}dl, \emph{Large triangle-free subgraphs in graphs
  without ${K}\sb 4$}, Graphs Combin. \textbf{2} (1986), no.~2, 135--144.
  \MR{89b:05124}

\bibitem{friedgut02}
E.~Friedgut, V.~R\"odl, A.~Ruci\'nski, and P.~Tetali, \emph{A sharp threshold
  for random graphs with monochromatic triangle in every edge coloring}, in
  preparation, 2002.

\bibitem{friedgut99:_sharp}
Ehud Friedgut, \emph{Sharp thresholds of graph properties, and the $k$-sat
  problem}, J. Amer. Math. Soc. \textbf{12} (1999), no.~4, 1017--1054, With an
  appendix by Jean Bourgain. \MR{2000a:05183}

\bibitem{JansonLuczakRucinski}
Svante Janson, Tomasz {\L}uczak, and Andrzej Ruci{\'n}ski, \emph{An exponential
  bound for the probability of nonexistence of a specified subgraph in a random
  graph}, Random graphs '87 (Pozna\'n, 1987), Wiley, Chichester, 1990,
  pp.~73--87. \MR{91m:05168}

\bibitem{janson00:_random_graph}
\bysame, \emph{Random graphs}, Wiley-Interscience, New York, 2000.
  \MR{2001k:05180}

\bibitem{Kohayakawa97Szemeredi}
Y.~Kohayakawa, \emph{Szemer\'edi's regularity lemma for sparse graphs},
  Foundations of computational mathematics (Rio de Janeiro, 1997), Springer,
  Berlin, 1997, pp.~216--230. \MR{99g:05145}

\bibitem{kohayakawa02:_raac}
Y.~Kohayakawa and V.~R\"odl, \emph{Szemer\'edi's regularity lemma and
  quasi-randomness}, Recent advances in algorithms and combinatorics, Springer,
  Berlin, 63pp., to appear, 2002.

\bibitem{KLRap3}
Yoshiharu Kohayakawa, Tomasz {\L}uczak, and Vojt{\v{e}}ch R{\"o}dl,
  \emph{Arithmetic progressions of length three in subsets of a random set},
  Acta Arith. \textbf{75} (1996), no.~2, 133--163. \MR{97b:11011}

\bibitem{kurek02:_ramsey}
Andrzej Kurek and Andrzej Ruci{\'n}ski, \emph{The sparsest {R}amsey graphs are
  complete graphs}, submitted, 2002.

\bibitem{luczak92:_ramsey}
Tomasz {\L}uczak, Andrzej Ruci{\'n}ski, and Bernd Voigt, \emph{Ramsey
  properties of random graphs}, J. Combin. Theory Ser. B \textbf{56} (1992),
  no.~1, 55--68. \MR{94b:05172}

\bibitem{rodl94}
Vojt{\v{e}}ch R{\"o}dl and Andrzej Ruci{\'n}ski, \emph{Random graphs with
  monochromatic triangles in every edge coloring}, Random Structures Algorithms
  \textbf{5} (1994), no.~2, 253--270. \MR{95a:05102}

\bibitem{RodlRucinski95}
\bysame, \emph{Threshold functions for {R}amsey properties}, J. Amer. Math.
  Soc. \textbf{8} (1995), no.~4, 917--942. \MR{96h:05141}

\bibitem{seress92}
{\'A}kos Seress, \emph{On {H}ajnal's triangle-free game}, Graphs Combin.
  \textbf{8} (1992), no.~1, 75--79. \MR{93a:05095}

\bibitem{szemeredi76}
Endre Szemer{\'e}di, \emph{Regular partitions of graphs}, Probl\`emes
  combinatoires et th\'eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay,
  Orsay, 1976), CNRS, Paris, 1978, pp.~399--401. \MR{81i:05095}

\end{thebibliography}

\end{document}
