%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% AMSLaTeX file for the paper                                        %
%                                                                    %
% INDUCED RAMSEY NUMBERS                                             %
%                                                                    %
% by Y. Kohayakawa, H.J. Pr\"omel, and V. R\"odl                     %
%                                                                    %
% Version of 5 September 1997                                        %
% (bibitems added to this file on 16 July 1998)                      %   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}
%\documentclass[reqno]{amsart}

\newtheorem{theorem}             {Theorem}       %[section]
\newtheorem{claim}     [theorem] {Claim}         %[section]
\newtheorem{lemma}     [theorem] {Lemma}         %[section]
\newtheorem{corollary} [theorem] {Corollary}     %[section]
\newtheorem{fact}      [theorem] {Fact}          %[section]
\newtheorem{conjecture}[theorem] {Conjecture}    %[section]
\newtheorem{problem}   [theorem] {Problem}       %[section]

\def\({\left(}
\def\){\right)}  
\def\<{\left\langle}
\def\>{\right\rangle}
\newcommand{\llfloor}{\left\lfloor}
\newcommand{\rrfloor}{\right\rfloor}
\newcommand{\llceil}{\left\lceil}
\newcommand{\rrceil}{\right\rceil}
\let\epsilon=\varepsilon
\let\rho=\varrho
\let\phi=\varphi
\def\e{{\rm e}}
\def\:{\colon}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\tildep{{\widetilde p}}
\def\tepsilon{{\widetilde\epsilon}}
\def\trho{{\widetilde\rho}}
\def\dXr{d_{\protect{\rm red}}^X}
\newcommand{\Prob}{{\mathbb P}}
\def\cB{{\mathcal B}}
\def\cG{{\mathcal G}}
\def\cL{{\mathcal L}}
\def\cP{{\mathcal P}}
\def\cR{{\mathcal R}}
\def\cS{{\mathcal S}}
\def\cT{{\mathcal T}}
\def\cY{{\mathcal Y}}
\newcommand{\cLAB}{{\cL}_{AB}}
\def\bfX{{\mathbf X}}
\def\bfA{{\mathbf A}}
\newcommand\ered{e_{\protect{\rm red}}}
\newcommand\Ered{E_{\protect{\rm red}}}
\newcommand\Nred{N_{\protect{\rm red}}}
\newcommand\NredR{N_{\protect{\rm red}}^\cR}
\newcommand{\rind}{r_{\protect{\rm ind}}}
\def\marrows#1{\;\mathop{\to}\limits^{#1}\;}
\def\dcup{\mathop{\cup}\limits^\cdot}
\newcommand{\twt}{w}
\def\sumell#1#2#3{\sum\nolimits^{(#1)}_{#2\neq#3}}
\newcommand{\Perm}{\protect{\rm Perm}}
\newcommand\bsigma{\bar\sigma}
\newcommand\Prop{{\mathbf P}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\yk#1{[\textit{yk}: \textsl{#1}]}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\assertion(#1){\smallbreak\noindent 
  {\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\catcode`@=11
%\def\openup{\afterassignment\@penup\dimen@=}
%\def\@penup{\advance\lineskip\dimen@
%  \advance\baselineskip\dimen@
%  \advance\lineskiplimit\dimen@}
%\def\eqalign#1{\null\,\vcenter{\openup\jot\m@th
%  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
%      \crcr#1\crcr}}\,}
%\newif\ifdt@p
%\def\displ@y{\global\dt@ptrue\openup\jot\m@th
%  \everycr{\noalign{\ifdt@p \global\dt@pfalse
%      \vskip-\lineskiplimit \vskip\normallineskiplimit
%      \else \penalty\interdisplaylinepenalty \fi}}}
%\def\@lign{\tabskip\z@skip\everycr{}} % restore inside \displ@y
%\def\displaylines#1{\displ@y
%  \halign{\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}\crcr
%    #1\crcr}}
%\def\eqalignno#1{\displ@y \tabskip\centering
%  \halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip
%    &$\@lign\displaystyle{{}##}$\hfil\tabskip\centering
%    &\llap{$\@lign##$}\tabskip\z@skip\crcr
%    #1\crcr}}
%\def\leqalignno#1{\displ@y \tabskip\centering
%  \halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip
%    &$\@lign\displaystyle{{}##}$\hfil\tabskip\centering
%    &\kern-\displaywidth\rlap{$\@lign##$}\tabskip\displaywidth\crcr
%    #1\crcr}}
%\catcode`@=12 % at signs are no longer letters
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\title{Induced Ramsey Numbers}
\author{Y.~Kohayakawa}
%\thanks{Partially supported by FAPESP (Proc.~96/4505--2) and by CNPq
%  (Proc.~300334/93--1 and ProTeM-CC-II Project ProComb).  Part of this work
%  was done while this author was visiting 
%  Humboldt-Universit\"at zu Berlin through PROBRAL project number~026/95, a
%  CAPES--DAAD exchange programme.}
\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{H.~J.~Pr\"omel}
%\thanks{Research partially supported by DFG project Pr~296/4--1 and
%  PROBRAL project number~026/95.} 
\address{Institut f\"ur Informatik, Humboldt-Universit\"at zu Berlin,
  Unter den Linden~6, 10099~Berlin, Germany}
\email{proemel@informatik.hu-berlin.de}
\author{V.~R\"odl}
%\thanks{Research partially supported by NSF grant DMS--9401559.  Part
%  of this work was done while this author was visiting the
%  Humboldt-Universt\"at zu Berlin through a Humboldt Professorship.} 
\address{Department of Mathematics and Computer Science, Emory
  University, Atlanta, GA~30322, USA}
\email{rodl@mathcs.emory.edu}
%
\dedicatory{Dedicated to the memory of Professor Paul Erd\H os}
%
\thanks{Research partially supported by PROBRAL project~026/95, a CAPES--DAAD
  exchange programme and Humboldt Stiftung.  The first author was partially
  supported by FAPESP (Proc.~96/04505--2), by CNPq (Proc.~300334/93--1 and
  ProTeM-CC-II Project ProComb), and by MCT/FINEP under PRONEX project 107/97.
  The second author was partially supported DFG project Pr~296/4--1.  The
  third author was partially supported by NSF grant DMS--9401559.}
\thanks{Part of this work was done while the first and the third authors were
  visiting Humboldt-Universit\"at zu Berlin.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subjclass{Primary 05C55, % Generalised Ramsey theory
  05C80;                  % Random graphs 
  Secondary: 05C35}       % Extremal problems
\keywords{Generalised Ramsey theory, induced subgraphs,
  random graphs}
%\date{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
  We investigate the \textit{induced Ramsey number}~$\rind(G,H)$ of
  pairs of graphs~$(G,H)$.  This number is defined to be the smallest
  possible order of a graph~$\Gamma$ with the property that, whenever
  its edges are coloured red and blue, either a red induced copy
  of~$G$ arises or else a blue induced copy of~$H$ arises.  We show
  that, for any~$G$ and~$H$ with~$k=|V(G)|\leq t=|V(H)|$, we have 
  \begin{equation*}
    \rind(G,H)\leq t^{Ck\log q},   
  \end{equation*}
  where~$q=\chi(H)$ is the chromatic number of~$H$ and~$C$ is some universal
  constant. Furthermore, we also investigate~$\rind(G,H)$ imposing some
  conditions on~$G$.  For instance, we prove a bound that is polynomial in
  both~$k$ and~$t$ in the case in which~$G$ is a tree.  Our methods of proof
  employ certain random graphs based on projective planes.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction and Main Results}
\label{sec:intro}
A fundamental problem in Ramsey theory is to determine or estimate the
Ramsey number for complete graphs.  Write~$R(k)$ for the smallest
integer~$n$ with the property that, if one colours the edges of the
complete graph on~$n$ vertices with colours red and blue, one
necessarily obtains a complete subgraph on~$k$ vertices all of whose
edges are coloured red, or else all of whose edges are coloured blue.
The number~$R(k)$, the existence of which follows from a classical
theorem of Ramsey~\cite{Ram}, is the \textit{Ramsey number} of the
complete graph on~$k$ vertices.

The best bounds that are currently known for~$R(k)$ imply that
$$
2^{1/2}\leq\liminf_{k\to\infty}R(k)^{1/k}
       \leq\limsup_{k\to\infty}R(k)^{1/k}
       \leq4.
$$
Thus, even the precise rate of the exponential growth of~$R(k)$ is
unknown.  Indeed, deciding whether~$\lim_{k\to\infty}R(k)^{1/k}$ exists, and
if so determining its value, are outstanding problems in the area.  For a
pleasant introduction to Ramsey theory in general, the reader is referred to
Graham, Rothschild, and Spencer~\cite{GRS}.  Ne\v set\v
ril~\cite{Nesetril95Handbook} gives a relatively concise survey on this vast
subject.  Numerical problems in this area are discussed by Graham and
R\"odl~\cite{GRo}.

In this paper, we are concerned with a counterpart to the theorem of
Ramsey for non-complete graphs.  Namely, we are interested in a result
proved independently by Deuber~\cite{Deu}, Erd\H os, Hajnal, and
P\'osa~\cite{EHP}, and R\"odl~\cite{RoThesis}, which states that, for
any pair of graphs~$G$ and~$H$, there is a graph~$\Gamma$ such that
\begin{equation}
  \label{eq:ind-arrows}
  \Gamma\to(G,H), 
\end{equation}
where the arrow notation in~(\ref{eq:ind-arrows}) above means that
whenever we colour the edges of~$\Gamma$ red and blue, either a red
induced copy of~$G$ arises, or else a blue induced copy of~$H$ arises.
This variant of Ramsey's theorem immediately raises a numerical
problem.

For any given graphs~$G$ and~$H$, let~$\rind(G,H)$ denote the smallest
integer~$n$ for which there exists a graph~$\Gamma$ on~$n$ vertices
satisfying~(\ref{eq:ind-arrows}).  We refer to~$\rind(G,H)$ as the
\textit{induced Ramsey number} of the pair~$(G,H)$.  Erd\H os
wrote~\cite[\S5]{ErdosCambridge83} (with a little change in the notation):
``Hajnal and I observed that if~$G_1$ and~$G_2$ have at most~$n$ vertices,
then
\begin{equation}
  \label{eq:EHdoubly}
  \rind(G_1,G_2)\leq2^{2^{n^{1+\epsilon}}}.
\end{equation}
We have never published the not entirely trivial proof
of~(\ref{eq:EHdoubly}) since Hajnal and I thought that perhaps 
\begin{equation}
  \label{eq:EHconj}
  \max\rind(G_1,G_2)=R(n).
\end{equation}

``Conjecture~(\ref{eq:EHconj}) is perhaps a little too optimistic, but
we have no counterexample.  Perhaps there is a better chance to
prove~$\rind(G_1,G_2)\leq 2^{cn}$.''

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Erd\H os raised the problem of determining or estimating~$\rind(H)$ as
%sharply as possible.  In fact, he observed that it is not even clear
%that the maximum of~$\rind(H)$ with~$H$ running over all graphs on~$t$
%vertices is not achieved by taking~$H=K^t$, the complete graph on~$t$
%vertices.  With Hajnal, he proved that 
%for any~$\epsilon>0$ as long as~$t=|V(H)|\geq t_0(\epsilon)$.
%The problem of
%deciding whether an exponential bound holds for \textit{any} graph~$H$
%was raised by Erd\H os and R\"odl (see~\cite{ErdosPrague74}):
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Writing~$\rind(H)$ for~$\rind(H,H)$, this latter problem of Erd\H
os~\cite{ErdosCambridge83}, already implicit in~\cite[\S{III}]{ErdosPrague74},
is then the following:

\begin{problem}\label{prob:exponential}
  Is there an absolute constant~$C$ such that for any graph~$H$ on~$t$
  vertices we have~$\rind(H)\leq2^{Ct}$?
\end{problem}

Techniques in R\"odl~\cite{RoThesis} imply that~$\rind(H,H)$ is indeed
exponential in~$t=|V(H)|$ if~$H$ is bipartite.  Note that if the answer to
Problem~\ref{prob:exponential} is positive, then the result is best possible
up to the value of~$C$, that is, there are graphs~$H$ for which~$\rind(H)$ is
exponential in~$t=|V(H)|$.  Indeed, it suffices to take~$H$ as the complete
graph on~$t$ vertices.

Our main result below, Theorem~\ref{thm:variant}, comes close to establishing
a positive answer to Problem~\ref{prob:exponential} in general.  In
particular, our result greatly strengthens the previous doubly exponential
bound~(\ref{eq:EHdoubly}) of Erd\H os and Hajnal.

Quite curiously, our result also comes close to settling the following
conjecture, which deals with the `asymmetric' induced Ramsey
number~$\rind(G,H)$.  Here, we are concerned with the case in which~$G$ is
some fixed graph and~$H$ is very large.

\begin{conjecture}\label{conj:smallG}
  For any graph~$G$, there is a constant~$f=f(G)$ that depends only
  on~$G$ such that, for any graph~$H$ on~$t$ vertices, we have
  $$
  \rind(G,H)\leq t^f.
  $$
\end{conjecture}

Our main result is as follows.

\begin{theorem}
  \label{thm:variant}
   Let~$G$ and~$H$ be graphs with~$|V(G)|=k$ and~$|V(H)|=t$, where~$k\leq t$,
   and suppose~$q=\chi(H)\geq2$. 
   Then 
   \begin{equation}
     \label{eq:thm:variant}
     \rind(G,H)\leq t^{Ck\log q}
   \end{equation}
   for some absolute constant~$C$.
\end{theorem}

Note that in the `diagonal case', in which~$G=H$, Theorem~\ref{thm:variant}
gives the bound
\begin{equation*}
 \rind(H)=\rind(H,H)\leq t^{Ct\log q},
\end{equation*}
which only fails to be a purely exponential bound in~$t=|V(H)|$ by a factor
of~$(\log t)(\log\chi(H))\leq(\log t)^2$ in the exponent.  Furthermore, note
that~(\ref{eq:thm:variant}) in Theorem~\ref{thm:variant} fails to be
polynomial in~$t$ only by a factor of~$\log\chi(H)$ in the exponent.  Thus,
Theorem~\ref{thm:variant} does indeed fall only a little short of settling
Problem~\ref{prob:exponential} and Conjecture~\ref{conj:smallG}.

Inequality~(\ref{eq:thm:variant}) is proved by showing that there is a
suitably small graph~$R$ for which~$R\to(G,H)$ holds.  This
graph~$R=R(\cP,H)$ is randomly constructed using a projective
plane~$\cP$ and the graph~$H$.  (The graph~$G$ plays no r\^ole in the
definition of~$R$.)  Roughly speaking, the graph~$R$ is obtained
from~$\cP$ and~$H$ by randomly embedding `blown-up copies' of~$H$ in
each line of~$\cP$.  (A `blow-up' of~$H$ is simply a graph obtained
from~$H$ by replacing each vertex of~$H$ by an independent set and
each edge of~$H$ by a suitably large complete bipartite graph.)  

The random graphs~$R=R(\cP,H)$ were considered before by Brown and
R\"odl~\cite{BrownRodl} and Eaton and R\"odl~\cite{eaton92}.  However,
in~\cite{BrownRodl,eaton92}, the authors investigate Ramsey properties
of these graphs with respect to \textit{vertex} colourings.  A similar
construction is studied by R\"odl and Winkler in~\cite{RodlWinkler},
where Ramsey properties with respect to orientations of graphs are
investigated.  More recently, \L uczak and R\"odl~\cite{LRo} confirmed
a conjecture of Trotter by showing that~$\rind(H)=t^{O(1)}$ if the
$t$-vertex graph~$H$ has bounded maximum degree.  The
graph~$R=R(\cP,H)$ is crucial in~\cite{LRo}.

Since~(\ref{eq:thm:variant}) fails to prove Conjecture~\ref{conj:smallG} in
full generality, we consider graphs~$G$ with some special structure.  To
describe a class of graphs~$G$ for which we are able to prove
Conjecture~\ref{conj:smallG}, we need to introduce a couple of definitions.

If~$G_1$ and~$G_2$ are two graphs, we let the \textit{join}~$G_1\vee
G_2$ of~$G_1$ and~$G_2$ be the graph obtained from the disjoint union
of~$G_1$ and~$G_2$ by adding all the $G_1$--$G_2$ edges.  Thus, for
instance, $K^{a,b}=E^a\vee E^b$, where~$K^{a,b}$ is the complete
bipartite graph with vertex classes of cardinalities~$a$ and~$b$,
and~$E^a$ denotes the $a$-vertex graph with no edges, and similarly
for~$E^b$.

Let~$\cS$ denote the smallest class of finite graphs that contains the
$1$-vertex complete graph and is closed under taking disjoint unions
and joins.  Following Erd\H os and Hajnal~\cite{ErdosHajnalConj}, we
call the graphs in~$\cS$ \textit{simple}.  Theorem~\ref{thm:EHsimple}
below verifies Conjecture~\ref{conj:smallG} in the case in which~$G$
is a simple graph.

\begin{theorem}\label{thm:EHsimple}
  For any simple graph~$G$, there is a constant~$f=f(G)$ that depends
  only on~$G$ such that, for any graph~$H$ on~$t$ vertices, we have
  $$
  \rind(G,H)\leq t^f.
  $$
\end{theorem}

The proof of Theorem~\ref{thm:EHsimple} will also be based on the
random graph~$R=R(\cP,H)$.  However, quite naturally, the choice of
certain parameters in the definition of this graph for this proof will
be different from the choice to be made in the proof of
Theorem~\ref{thm:variant}.

A basic case that is not covered in Theorem~\ref{thm:EHsimple} is the
one in which~$G$ is a tree.  As one may expect, this case can be
handled quite easily.

\begin{theorem}\label{thm:trees}
  For any tree~$T$ and arbitrary graph~$H$, we have
  \begin{equation}
    \label{eq:trees}
    \rind(T,H)\leq ck^2t^4\(\frac{\log(kt^2)}{\log\log\log(kt^2)}\)^2, 
  \end{equation}
  where~$k=|V(T)|$, $t=|V(H)|$, and~$c$ is some absolute constant. 
\end{theorem}

Thus, Theorem~\ref{thm:trees} tells us that~$\rind(T,H)$ is polynomial
in both~$k=|V(T)|$ and~$t=|V(H)|$.  Our proof of this result is
simple, and we have not put much effort in obtaining the best
exponents in~(\ref{eq:trees}).  Let us mention that Beck has
investigated the problem of estimating the \textit{induced size-Ramsey
number} of a given tree~$T$, which is defined to be the minimal number
of edges in a graph~$\Gamma=\Gamma(T)$ such that~$\Gamma\to(T,T)$. 
Indeed, in~\cite{BeckB}, Beck proves that if~$T$ is a tree with~$n$
edges and~$n$ is larger than some absolute constant, then there is a
graph~$\Gamma$ with less than 
$$
n^3(\log n)^4
$$
edges such that~$\Gamma\to(T,T)$. 

This paper is organised as follows.  The random graph~$R=R(\cP,H)$ is defined
in Section~\ref{sec:prelims}, where auxiliary results concerning projective
planes are also given.  We also give in Section~\ref{sec:prelims} a couple of
properties of~$R=R(\cP,H)$ that are crucial later on in the proofs of
Theorems~\ref{thm:variant} and~\ref{thm:EHsimple}, given in
Sections~\ref{sec:general} and~\ref{sec:simple}.  The induced Ramsey number
for trees versus general graphs is studied in Section~\ref{sec:trees}.  Our
very short final section is devoted to some concluding remarks.

As the reader will observe, we try to isolate, whenever possible, the
probabilistic parts of our arguments in the proofs of
Theorems~\ref{thm:variant} and~\ref{thm:EHsimple}.  For instance,
Section~\ref{sec:monochro} is entirely deterministic in nature.  The only
probabilistic component in the proof of Theorem~\ref{thm:variant} is, in fact,
an application of Corollary~\ref{cor:co2.7} of Section~\ref{sec:Pi-lemmas},
made in Section~\ref{sec:proof-variant}.  Needless to say, this probabilistic
component is crucial for our argument.

Below, we write~$a\ll b$ to mean that~$a/b\to0$ as~$n\to\infty$, and similarly
for~$\gg$.  We also write~$a\sim b$ to mean that~$a/b\to1$ as~$n\to\infty$.
Moreover, for $A>0$, $B>0$ and~$\delta>0$, we write~$A\sim_\delta B$
if~$1/(1+\delta)<A/B<1+\delta$.  In the sequel, the logarithms without
specified bases are to the base~$\e$.

\section{The Construction and Preliminary Lemmas}
\label{sec:prelims}

\subsection{The construction}
\label{sec:construct}
Let a projective plane~$\cP=(V,\cL)$ with~$|V|=|\cL|=n$ and a
graph~$H$ be given.  We shall construct a random
graph~$R=R_n=R_n(\cP,H)$ based on~$\cP$ and~$H$ that will have
interesting Ramsey properties with respect to `small' graphs~$G$ and
the graph~$H$.  Note in particular that the definition of~$R$ will not
depend on the graph~$G$.

To describe our construction, suppose that, for each line~$L\in\cL$, we have a
partition~$L=\bigcup_{v\in V(H)}L_v$ of~$L$ whose parts~$L_v$ are indexed by
the vertices~$v\in V(H)$ of~$H$.  Denote this partition by~$\Pi_L$, and
set~$\Pi=(\Pi_L)_{L\in\cL}$.  We define the graph~$R=R_n(\cP,H,\Pi)$ as
follows.  The vertex set of~$R$ is~$V$.  To define the edge set of~$R$,
suppose~$a$, $b\in V$ are two distinct points in~$\cP$.  Then there is a
unique line~$L\in\cL$ that contains both~$a$ and~$b$.  Consider the
partition~$\Pi_L\in\Pi$ of~$L$, and suppose~$a\in L_u$ and~$b\in L_v$.  Then
$$
ab\in E(R)\text{ if and only if }uv\in E(H).
$$

To define the \textit{random} graph~$R=R_n(\cP,H)$, we pick the family
of partitions~$(\Pi_L)_{L\in\cL}$ randomly.  For each~$L\in\cL$, the
partition~$\Pi_L$ is chosen uniformly at random from all the
partitions of~$L$ indexed by~$V(H)$.  Equivalently, for each~$x\in L$,
we choose a vertex~$v\in V(H)$ independently and uniformly at random
and let~$x\in L_v$.  The choices of the~$\Pi_L$ are made independently
for all~$L\in\cL$.  This defines a random family of
partitions~$\Pi=(\Pi_L)_{L\in\cL}$, and we define our random graph~$R$
by letting
$$
R=R_n(\cP,H)=R_n(\cP,H,\Pi).
$$
Note that the randomness of~$R=R_n(\cP,H,\Pi)$ comes solely from the
random choice of~$\Pi$.  Once~$\Pi$ is chosen, the graph~$R$ is
determined. 

\subsection{Lemmas on projective planes}
\label{sec:projective}
Naturally, the key to a good understanding of the random
graph~$R=R_n(\cP,H)$ is a good understanding of the random
family~$\Pi=(\Pi_L)_{L\in\cL}$.  In this section, we shall review a
few facts about projective planes that will be needed in
Section~\ref{sec:Pi-lemmas}, where we analyse the structure of a
typical family~$\Pi=(\Pi_L)_{L\in\cL}$.

We start with a lemma due to Eaton and R\"odl~\cite{eaton92}.

\begin{lemma}\label{lemma:EaRo}%{\protect{\rm[Eaton, R\"odl]}} 
  Let~$(V,\cL)$ be a projective plane of order~$p$ and~$n=p^2+p+1$.
  Let~$X\subset V$ and~$\cY\subset\cL$ be given, and suppose~$|X|=\alpha
  n$ and~$|\cY|=\beta n$.  Then 
  \begin{multline*}%\tag*\qed
  \frac{\alpha\beta n^2}{p+\sqrt p+1}
      \(1-\frac{1+O(n^{-1/4})}{\sqrt{\alpha\beta\sqrt n}}\)
   \le\sum_{L\in\cY}|X\cap L|\\
   \le\frac{\alpha\beta n^2}{p+\sqrt p+1} 
       \(1+\frac{1+O(n^{-1/4})}{\sqrt{\alpha\beta\sqrt n}}\).\qed
  \end{multline*}
\end{lemma}

\begin{corollary}\label{cor:co1}
  With the notation as above, if~$\alpha\beta\geq\omega n^{-1/2}$,
  then 
  $$
  \sum_{L\in\cY}|X\cap L|
    =\(1+O\(\frac1{\sqrt\omega}\)\)\alpha\beta n^{3/2}.\eqno\qed
  $$
\end{corollary}

In the corollary below, $O_1(a)$ denotes a term~$b$ that
satisfies~$|b|\leq a$.

\begin{corollary}\label{cor:co2}
   Suppose~$X\subset V$ and~$\alpha=|X|/n$.  Then, if~$\beta=\beta(n)$
   satisfies $\alpha\beta\geq2\omega n^{-1/2}$ for some
   function~$\omega=\omega(n)\to\infty$, we
   have 
   \begin{equation}
     \label{eq:sim-cond}
     |X\cap L|=\(1+O_1\(\frac{\log\omega}{\sqrt\omega}\)\)\alpha\sqrt n
   \end{equation}
   for all but fewer than~$\beta n$ lines~$L\in\cL$, as long as~$n\geq
   n_0(\omega)$.  
\end{corollary}
\begin{proof}
Suppose~(\ref{eq:sim-cond}) fails.  Then there is a set of
lines~$\cY\subset\cL$ with~$|\cY|=\llceil\beta n/2\rrceil$ such that
either 
\begin{equation}
  \label{eq:too-many}
  |X\cap L|>\(1+\frac{\log\omega}{\sqrt\omega}\)\alpha\sqrt n
\end{equation}
for all~$L\in\cY$, or else
\begin{equation}
  \label{eq:too-few}
  |X\cap L|<\(1-\frac{\log\omega}{\sqrt\omega}\)\alpha\sqrt n
\end{equation}
for all~$L\in\cY$.  Suppose~(\ref{eq:too-many}) happens.
Summing~(\ref{eq:too-many}) over all~$L\in\cY$, we have, by
Corollary~\ref{cor:co1}, 
\begin{equation*}
% \label{eq:contradiction}
  \(1+\frac{\log\omega}{\sqrt\omega}\)\alpha\sqrt n|\cY|
    <\sum_{L\in\cY}|X\cap L|
    =\(1+O\(\frac1{\sqrt\omega}\)\)\alpha\sqrt n|\cY|,
\end{equation*}
which contradicts Corollary~\ref{cor:co1} if~$n\geq n_0(\omega)$,
since~$\omega=\omega(n)\to\infty$.  The case in
which~(\ref{eq:too-few}) holds for all~$L\in\cY$ is similar.
\end{proof}

Let us remark that, clearly, the~$O_1$ term in the result above may be
chosen to be anything that is sufficiently larger
than~$\omega^{-1/2}$.  Note also that Corollary~\ref{cor:co2} only
concerns sets~$X$ with~$|X|\gg\sqrt n$, since we need~$\beta\leq1$ and
hence~$\alpha\beta\gg n^{-1/2}$ can only hold if~$\alpha\gg n^{-1/2}$.

In view of Corollary~\ref{cor:co2}, we make the following definition.
Let~$X\subset V$, $L\in\cL$, and~$\delta>0$ be given.  We say that the
line~$L$ is \textit{$(X,\delta)$-normal} if
$$
|X\cap L|\sim_\delta\frac{|X|}{\sqrt n}\,.
$$
(We recall that we write~$A\sim_\delta B$ if~$1/(1+\delta)<A/B<1+\delta$.)
Let us set 
\begin{equation}
  \label{eq:cB(X,delta)}
  \cB(X,\delta)=\{L\in\cL\:
    \text{$L$ is \textit{not} $(X,\delta)$-normal}\}.
\end{equation}
Note that Corollary~\ref{cor:co2} implies that~$|\cB(X,\delta)|<\beta
n$ if~$X\subset V$ satisfies~$\beta|X|\gg\sqrt n$ and~$n$ is large
enough.

\subsection{A few lemmas on~$\Pi=(\Pi_L)_{L\in\cL}$}
\label{sec:Pi-lemmas}
To study the random graphs~$R=R_n(\cP,H)$, we need to investigate the
random family of partitions~$\Pi=(\Pi_L)_{L\in\cL}$ that is used to
define those random graphs.  In fact, in this section, we assume
that~$\Pi=(\Pi_L)_{L\in\cL}$ is a family of random partitions of
the~$L\in\cL$, with each~$\Pi_L$ an independent random partition
of~$L$, uniformly chosen from all the partitions of~$L$ indexed
by~$[t]=\{1,\dots,t\}$, for some given integer~$t$.  We shall only be
concerned with large~$t$ and large~$n$.  Thus, the inequalities below
need only hold for large enough~$t$ and~$n$.  Before we proceed, let
us stress that the graph~$H$ will not play any r\^ole in this section.

We start with a definition that will be very important in the sequel.
Let~$L\in\cL$, $X\subset V$, and~$\delta>0$ be given.  Also, let a
fixed family of $[t]$-indexed partitions~$\Pi=(\Pi_L)_{L\in\cL}$ be
given.  We then say that~$L$ is \textit{$(X,\delta,\Pi)$-normal} if
$$
|X\cap L_i|\sim_\delta\frac{|X|}{t\sqrt n}
$$
for all~$1\leq i\leq t,$ where~$L_i$ is the~$i$th block of the
partition~$\Pi_L$ of~$L$.  A moment's thought shows that if a line~$L$ is
$(X,\delta,\Pi)$-normal, then it is also $(X,\delta)$-normal, whereas the
converse holds only if the partition~$\Pi_L$ of~$L$ splits~$X\cap L$
`judiciously.'

Let us set
\begin{equation}
  \label{eq:cB(X,delta,Pi)}
  \cB(X,\delta,\Pi)=\{L\in\cL\:
    \text{$L$ is \textit{not} $(X,\delta,\Pi)$-normal}\}.
\end{equation}
Our next simple lemma says that the probability that many
$(X,\delta/2)$-normal lines should \textit{fail} to be
$(X,\delta,\Pi)$-normal is very small.

\begin{lemma}\label{fact:f1}
  Fix~$\delta>0$ and~$X\subset V$.  Then
  $$
    \Prob\Big\{\big|\cB(X,\delta,\Pi)\setminus\cB(X,\delta/2)\big|
                \geq t^2\sqrt n\Big\}
        <\exp\(-c_\delta t|X|+\frac12t^2\sqrt n\log n\), 
  $$
  where~$c_\delta$ is some positive constant that depends only
  on~$\delta$.  
\end{lemma}
\begin{proof}
  Let a $(X,\delta/2)$-normal line~$L\in\cL\setminus\cB(X,\delta/2)$
  be fixed (cf.~(\ref{eq:cB(X,delta)})).  Then, by definition, 
  \begin{equation*}
    |X\cap L|\sim_{\delta/2}\frac{|X|}{\sqrt n}\,.
  \end{equation*}
  Fix~$1\leq i\leq t$.  By Chernoff's inequality, we have
  \begin{equation*}
    \Prob\left\{|X\cap L_i|\sim_\delta\frac{|X|}{t\sqrt n}\right\}
      \geq1-\exp\(-c_\delta\frac{|X|}{t\sqrt n}\)
  \end{equation*}
  for some~$c_\delta>0$ that depends only~$\delta$.  Hence
  \begin{equation*}
    \Prob\(\text{$L$ is not $(X,\delta,\Pi)$-normal}\)
      \leq t\exp\(-c_\delta\frac{|X|}{t\sqrt n}\).
  \end{equation*}
  Since the partitions~$\Pi_L$ ($L\in\cL$) are chosen independently,
  we have
  \begin{multline*}
    \Prob\Big\{\big|\cB(X,\delta,\Pi)\setminus\cB(X,\delta/2)\big|
                \geq t^2\sqrt n\Big\}\\
    \leq\binom n{\lceil t^2\sqrt n\rceil}
         \(t\exp\(-c_\delta\frac{|X|}{t\sqrt n}\)\)
          ^{\lceil t^2\sqrt n\rceil}\\
    \leq\exp\(-c_\delta t|X|+\frac12t^2\sqrt n\log n\),
  \end{multline*}
  as required.
\end{proof}

Corollary~\ref{cor:co2} and Lemma~\ref{fact:f1} have the following
immediate consequence.

\begin{corollary}\label{cor:oneXbad}
  Let functions~$\alpha=\alpha(n)$ and~$\beta=\beta(n)$ such
  that~$\alpha\beta\gg n^{-1/2}$ be given, and suppose that a
  constant~$\delta>0$ is fixed.  Then the probability that there is a
  set~$X\subset V$ with~$|X|\geq\alpha n$ such that
  $$
  |\cB(X,\delta,\Pi)|\geq t^2\sqrt n+\beta n
  $$
  is at most
  \begin{equation}
    \label{eq:estimate2.6}
    \sum_{\alpha n\leq r\leq n}
      \binom nr\exp\(-c_\delta tr+\frac12t^2\sqrt n\log n\).
  \end{equation}
  \qed
\end{corollary}

To state the main result of this section concisely, we need to
introduce some notation.  Fix~$\delta>0$.
Suppose~$\bfX=(X_i)_{i=1}^t$ is a family of subsets~$X_i\subset V$
of~$V$, and suppose~$\Pi=(\Pi_L)_{L\in\cL}$ is a fixed family of
$[t]$-indexed partitions of the lines of~$\cP=(V,\cL)$.  Then we let
\begin{equation}
  \label{eq:cLbfXdeltaPi}
  \cL(\bfX,\delta,\Pi)=\{L\in\cL\:
    \text{$L$ is $(X_i,\delta,\Pi)$-normal for all~$i\in[t]$}\}.
\end{equation}
Thus, a line~$L\in\cL$ belongs to~$\cL(\bfX,\delta,\Pi)$ if and only if 
\begin{equation}
  \label{eq:XiLjjudicious}
  |X_i\cap L_j|\sim_\delta\frac{|X|}{t\sqrt n}
\end{equation}
for all~$i$ and~$j\in[t]$.  Moreover,
$\cL(\bfX,\delta,\Pi)=\cL\setminus\bigcup_{1\leq i\leq t}\cB(X_i,\delta,\Pi)$
(cf.~(\ref{eq:cB(X,delta,Pi)})).  When studying the subgraphs of the
graph~$R=R_n(\cP,H,\Pi)$, we shall need to look at \textit{families} of
$t$~sets of vertices~$\bfX=(X_i)_{i=1}^t$, and we shall be interested in the
lines that intersect these $t$~sets in the `expected way.'  The
set~$\cL(\bfX,\delta,\Pi)$ of lines of~$\cP$ defined above is the set of such
`interesting' lines.
  
Given constants~$0<\epsilon<1/2$, $\delta>0$, and~$0<\eta<1$, and a
family~$\Pi=(\Pi_L)_{L\in\cL}$ of $[t]$-indexed partitions, we
let~$\Prop(\epsilon,\delta,\eta,\Pi)$ denote the following property:
\assertion(*) For all~$\bfX=(X_i)_{i=1}^t$ with~$X_i\subset V$ such
that $|X_i|\geq n^{1/2+\epsilon}$ for all~$i\in[t]$, we have
$$
|\cL(\bfX,\delta,\Pi)|\geq(1-\eta)n.
$$
\endassertion
%
It is probably worth at this point to unfold the definitions to give a more
direct formulation of property~$\Prop(\epsilon,\delta,\eta,\Pi)$: the
family~$\Pi$ satisfies~$\Prop(\epsilon,\delta,\eta,\Pi)$ if and only if, for
all~$\bfX$ as in~(*), at least~$(1-\eta)n$ lines~$L\in\cL$ are such
that~(\ref{eq:XiLjjudicious}) holds for all~$i$ and~$j\in[t]$.

Corollary~\ref{cor:oneXbad} has the following consequence that
will be crucial in our study of the random graph~$R=R_n(\cP,H)$. 

\begin{corollary}\label{cor:co2.7}
  Let constants~$0<\epsilon\leq1/3$, $\delta>0$, and~$0<\eta<1$ be fixed.
  Suppose~$t=t(n)$ is such that~$\log n\ll t\ll n^{\epsilon/2}$.  Then
  $$
  \Prob\big\{\Prop(\epsilon,\delta,\eta,\Pi)\text{ holds}\big\}\to1
  $$
  as~$n\to\infty$.  In particular, if~$n\geq
  n_0(\epsilon,\delta,\eta,t)$, there is a family of
  $[t]$-indexed partitions~$\Pi=(\Pi_L)_{L\in\cL}$ for
  which~$\Prop(\epsilon,\delta,\eta,\Pi)$ holds.
\end{corollary}
\begin{proof}
  Let~$\alpha=\alpha(n)=n^{-1/2+\epsilon}$
  and~$\beta=\beta(n)=n^{-\epsilon/2}$.  Simple calculations show that
  \begin{equation*}
%   \label{eq:llnt}
    t^2\sqrt n+\beta n\ll n/t,
  \end{equation*}
  and that the quantity in~(\ref{eq:estimate2.6}) tends to~$0$
  as~$n\to\infty$.  Thus, Corollary~\ref{cor:oneXbad} says that, with
  probability tending to~$0$ as~$n\to\infty$, every~$X\subset V$
  with~$|X|\geq n^{1/2+\epsilon}$ is such that
  \begin{equation*}
%   \label{eq:BXdeltaPi}
    |\cB(X,\delta,\Pi)|<t^2\sqrt n+\beta n\ll n/t.
  \end{equation*}
  In particular, given any~$\bfX=(X_i)_{i=1}^t$ as in~(*), we have
  $$
  \Big|\bigcup_{1\leq i\leq t}\cB(X_i,\delta,\Pi)\Big|\ll n
  $$
  with probability approaching~$1$ as~$n\to\infty$.  Thus
  Corollary~\ref{cor:co2.7} follows. 
\end{proof}

\subsection{The pseudorandomness of~$R=R_n(\cP,H,\Pi)$}
\label{sec:pseudorandomness}
Fix a graph~$H$ and let~$\cP$ be a projective plane.  Consider the
graph~$R=R_n(\cP,H,\Pi)$ defined in Section~\ref{sec:construct},
where~$\Pi=(\Pi_L)_{L\in\cL}$ is some family of $V(H)$-indexed
partitions of the lines of~$\cP$.  

Let~$\gamma$ denote the edge-density~$e(H){\binom t2}^{-1}$ of~$H$,
where as customary~$e(H)$ stands for the number of edges in~$H$.
Later we shall see that, in the proofs of Theorems~\ref{thm:variant}
and~\ref{thm:EHsimple}, we may assume that~$\gamma$ is close to~$1/2$.
Thus, in this section, we assume that
\begin{equation}
  \label{eq:gamma1/2}
  3/7\leq\gamma\leq4/7.
\end{equation}
Our aim is to show that if~$\Prop(\epsilon,\delta,\eta,\Pi)$
holds for suitably small parameters~$\epsilon$, $\delta$, and~$\eta$,
any two disjoint and reasonably large sets~$A$ and~$B\subset V$ of
vertices of the graph~$R=R_n(\cP,H,\Pi)$ are connected by
about~$\gamma|A||B|$ edges.  In other words, the graph~$R$ is `pseudorandom.' 

\begin{lemma}\label{lem:l2}
  Let~$0<\epsilon<1/2$ and $0<\delta\leq1$ be fixed.
  Suppose~$\Pi=(\Pi_L)_{L\in\cL}$ is a family of $V(H)$-indexed
  partitions of the lines of~$\cP$.  Furthermore, suppose that the
  property~$\Prop(\epsilon,\delta/5,3\delta/40,\Pi)$ holds and
  that~$t\geq40/3\delta$.  Then the graph~$R=R_n(\cP,H,\Pi)$ is such
  that, for every~$A$, $B\subset V(R)$ with~$A\cap B=\emptyset$
  and~$|A|$, $|B|\ge n^{1/2+\epsilon}$, the number of edges~$e(A,B)$
  between~$A$ and~$B$ satisfies
  \begin{equation}
    \label{eq:lem:l2}
    e(A,B)\sim_\delta\gamma|A||B|.
  \end{equation}
\end{lemma}
\begin{proof}
  Let~$\cLAB$ be the set of lines~$L\in\cL$ that are both
  $(A,\delta/5,\Pi)$- and $(B,\delta/5,\Pi)$-normal.  Since
  property~$\Prop(\epsilon,\delta/5,3\delta/40,\Pi)$ holds, we know
  that
  \begin{equation}
    \label{eq:cLAB}
    |\cLAB|\geq(1-3\delta/40)n.
  \end{equation}
  By the definition of~$\cLAB$, for any line~$L\in\cLAB$ we have
  $$
  |L_v\cap A|\sim_{\delta/5}\frac{|A|}{t\sqrt{n}}
    \quad\mbox{and}\quad
    |L_v\cap B|\sim_{\delta/5}\frac{|B|}{t\sqrt{n}}
  $$
  for every~$v\in V(H)$, where~$L=\bigcup_{v\in V(H)}L_v$ is the
  partition~$\Pi_L$ of~$L$.  In particular, if~$uv\in E(H)$, we have
  \begin{equation}
    \label{eq:no-edges}
    \sim_{3\delta/5}\frac{|A||B|}{t^2n}
  \end{equation}
  edges joining the sets~$L_u\cap A$ and~$L_v\cap B$, and similary
  for~$L_v\cap A$ and~$L_u\cap B$. Furthermore, if~$uv\not\in E(H)$, the
  number of non-edges between~$L_u\cap A$ and~$L_v\cap B$, and similarly
  between~$L_v\cap A$ and~$L_u\cap B$, is also given by~(\ref{eq:no-edges}). 

  Therefore
  \begin{multline*}
    e(A,B)\ge\sum_{L\in\cLAB}\sum_{uv\in E(H)}
        \big\{|L_u\cap A||L_v\cap B|+|L_v\cap A||L_u\cap B|\big\}\\
     \sim_{3\delta/5}|\cLAB|2\frac{|A||B|}{t^2n}\gamma{\binom t2}
     \geq\frac1{1+3\delta/4}\gamma|A||B|,
  \end{multline*}
  where in the last inequality we used~(\ref{eq:cLAB}) and the fact
  that~$t\geq40/3\delta$ and~$\delta\leq1$.  Similarly, we infer that the
  number of non-edges between~$A$ and~$B$ is at least
  $$
  \frac{1-\gamma}{1+3\delta/4}|A||B|.
  $$
  Using that~$\gamma\geq3/7$ (cf.~(\ref{eq:gamma1/2})), we may now
  deduce from straightforward computations that~(\ref{eq:lem:l2})
  follows. 
\end{proof}

We observe that the proof above only made use of a weak form of
property~$\Prop(\epsilon,\delta/5,3\delta/40,\Pi)$.  Indeed, this property
concerns families~$\bfX$ of~$t$ elements, but in the proof above we were only
concerned about the \textit{pair} of sets~$\{A,B\}$.  

\subsection{Blow-ups of~$H$ in~$R=R_n(\cP,H,\Pi)$}
\label{sec:blowups}
In Section~\ref{sec:pseudorandomness} above, we observed that the
graph~$R=R_n(\cP,H,\Pi)$ tends to have all its edges uniformly spread
over~$V(R)$.  The usual binomial random graphs~$G_{n,p}$ also have this
property, and hence the random graphs~$R=R_n(\cP,H)$ and~$G_{n,p}$
(with~$p=\gamma$) may be expected to behave similarly.  However, one sees
right away a crucial difference between these graphs: $R=R_n(\cP,H)$ is
extremely rich in copies of~$H$.  Indeed, each line of~$\cP$ is very likely to
induce a `very fat' blown-up copy of~$H$.  This feature will be crucial in our
considerations.

In what follows, if~$s\geq1$ is an integer, we shall write~$H_s$ for
the \textit{$s$-fold blow-up} of~$H$, namely, the graph on~$s|V(H)|$
vertices that we obtain from~$H$ by replacing each vertex of~$H$ by an
independent set of cardinality~$s$ and each edge of~$H$ by a complete
bipartite graph~$K^{s,s}$.  The following simple lemma will be needed
in the sequel.

\begin{lemma}\label{claim:cl2}
  Every red-blue edge colouring of~$H_s$ that contains no blue copy
  of~$H$ must contain at least~$s^2$ red edges.
\end{lemma}
\begin{proof}
  Let us say that a copy~$H'$ of~$H$ in~$H_s$ is \textit{transversal}
  if~$|V(H')\cap V_x|=1$ for all~$x\in V(H)$, where~$V_x$ is the independent
  set of vertices of~$H_s$ that is naturally associated to~$x\in V(H)$.
  Clearly~$H_s$ has~$s^t$ transversal copies of~$H$.  On the other hand, each
  edge is contained in~$s^{t-2}$ transversal copies of~$H$.  Thus, at
  least~$s^t/s^{t-2}=s^2$ red edges are needed to prevent a transversal blue
  copy of~$H$.  This proves Lemma~\ref{claim:cl2}.
\end{proof}

\section{The General Estimate}
\label{sec:general}

Our aim in this section is to give a proof of
Theorem~\ref{thm:variant}.  Since our proof is fairly long and is
based on a few separate ideas, we shall sketch the general approach
before we start the proof proper.  

Let graphs~$G$ and~$H$ as in Theorem~\ref{thm:variant} be given.  A
simple argument shows that we may assume that the
edge-density~$e(H){\binom t2}^{-1}$ of~$H$ is, say, between~$3/7$
and~$4/7$.  As mentioned in the introduction, the main idea is to make
use of the random graphs~$R=R_n(\cP,H)$, defined in
Section~\ref{sec:construct}.

The two key properties of~$R$ for the arguments in this section are the
following: (\textit{i})~$R$ is a pseudorandom graph, in the sense that its
edges are uniformly distributed (with density similar to the density of~$H$),
and (\textit{ii})~any collection of~$t$ pairwise disjoint sets $X_1,\dots,X_t$
of vertices of~$R$ induce many `fat' blow-ups of~$H$, as long as the~$X_i$ are
all sufficiently large.

Suppose now that the edges of our graph~$R$ have been coloured with red and
blue.  Property~(\textit{i}) may be used to show that any appropriately large
set~$S$ of vertices of~$R$ that is `uniformly rich' in red edges must induce a
red copy of~$G$.  Roughly speaking, we shall consider a set~$S$ uniformly rich
in red edges if~$S$, as well as all large subsets of~$S$, induce sufficiently
many red edges.  (To be precise, we shall define the term \textit{hereditarily
  $\epsilon$-red-rich} in Section~\ref{sec:subsub2.5.1} to formalise this
notion of uniform richness.)

On the other hand, property~(\textit{ii}) may be used to show that any
collection of $t$~suitably large sets of vertices of~$R$ is forced to induce a
blue copy of~$H$, as long as the density of the red edges across these sets is
small.  The proof of the fact that~$R\to(G,H)$ is then reduced to showing that
either~$R$ has a set of vertices that is `uniformly rich' in red edges, or
else~$R$ has~$t$ suitably large sets of vertices that induce, across them,
very few red edges.

Let us now start the proof of Theorem~\ref{thm:variant}.

\subsection{The main lemma}
\label{sec:main-lemma}
For technical reasons, it will be convenient to prove first the following
restricted version of Theorem~\ref{thm:variant}.

\begin{lemma}
  \label{lem:variant}
  There exist absolute constants~$t_0$ and~$C$ for which the following holds.
  Let~$G$ and~$H$ be graphs with~$|V(G)|=k\geq2$ and~$|V(H)|=t\geq t_0$,
  where~$t\geq k^2$.  Write~$\gamma=e(H){\binom t2}^{-1}$ for the
  edge-density of~$H$, and suppose~$3/7\leq\gamma\leq4/7$.  Suppose
  furthermore that~$H$ 
  has a proper colouring~$V(H)=\bigcup_{1\leq i\leq q}V_i$ with all the~$V_i$
  of cardinality~$\twt=t/q$, where~$q=\chi(H)\geq2$.  Then 
  $$
  \rind(G,H)\leq t^{Ck\log q}.
  $$
\end{lemma}

We now sketch an argument that shows that Lemma~\ref{lem:variant} implies
Theorem~\ref{thm:variant}.  Thus, let graphs~$G$ and~$H$ as in
Theorem~\ref{thm:variant} be given.  In particular, we have~$t\geq k$.

Let us first observe that~$t$ may be assumed to be larger than any
fixed constant.  Indeed, recalling the existence of
graphs~$\Gamma=\Gamma(G,H)$ for which~$\Gamma\to(G,H)$ for any
given~$G$ and~$H$ (see~\cite{Deu,EHP,RoThesis}), we may exclude from
our consideration any bounded number of pairs~$(G,H)$, since we may
choose the constant~$C$ in~(\ref{eq:thm:variant}) sufficiently large
to cover this bounded number of cases.  Moreover, by adding fewer
than~$q=\chi(H)$ isolated vertices to~$H$, we may assume that~$q$
divides~$t$.

Now fix a proper vertex colouring~$V(H)=V_1\cup\cdots\cup V_q$ of~$H$.
Add~$t^2/q-|V_i|$ isolated vertices to~$V_i$ for all~$i$ to obtain a
graph~$H'$.  Note that now we have~$t^2$ vertices.  Now, a little
thought shows that we may add edges to~$H'$, each of them incident to
at least one vertex in~$V(H')\setminus V(H)$ and all of them
respecting the $q$-colouring we started with, and, furthermore, in
such a way that the graph~$H''$ that we obtain is such
that~$\gamma=e(H''){\binom{t^2}2}^{-1}$ lies between~$3/7$ and~$4/7$
(here we also use that~$t\geq t_0$ for some large enough
constant~$t_0$).  

Let us outline an easy argument to show that we may indeed obtain the
graph~$H''$ as required.  Note that the only thing to check is whether we can
accommodate the condition on the density of~$H''$.  If we add to~$H'$ all the
edges allowed by the other two conditions, we get at least about
$$
\(1-{\frac1q}\){\binom{t^2}2}-{\binom t2}
$$
new edges.  Thus, even if~$q=2$, we have at least
about~$\frac12{\binom{t^2}2}$ edges if~$t$ is large.  On the other hand, if we
do not add any edge to~$H'$, we have at most~${\binom t2}$ edges out
of~${\binom{t^2}2}$, which gives a density far smaller than~$1/2$ if~$t$ is
large.  Thus the graph~$H''$ as required does exist.

It now suffices to apply Lemma~\ref{lem:variant} to~$H''$ to deduce
that there is a graph~$\Gamma$ such that~$\Gamma\to(G,H'')$ and such
that~$|\Gamma|\leq(t+q-1)^{2Ck\log q}$, where~$C$ is the constant in
Lemma~\ref{lem:variant}.  Theorem~\ref{thm:variant} follows, since
clearly $\Gamma\to(G,H)$.

In the rest of Section~\ref{sec:general}, we
investigate~$R=R_n(\cP,H)$ with the aim of showing that~$R\to(G,H)$
with positive probability, even if~$n$ is not too large with respect
to~$k$ and~$t$.  More precisely, we shall prove the following
statement.

\assertion(\dag) There exists an absolute constant~$t_0$ such that,
for any graphs~$G$ and~$H$ as in Lemma~\ref{lem:variant}, there is an
integer~$n=n(k,t,q)$ with
\begin{equation*}
% \label{eq:n-upbd}  
  n\leq4t^{1000k\log q}, 
\end{equation*}
where~$q=\chi(H)$, such that
$$
R=R_n(\cP,H)\to(G,H)
$$
holds with positive probability.  
\endassertion

We shall not try to optimise our constants.  In particular, the
constant~$1000$ in~(\dag) is clearly not optimal.  We also remark that
our proof will in fact show a stronger Ramsey property
of~$R=R_n(\cP,H)$.  Write~$\cG^k$ for the family of all graphs on~$k$
vertices.  Our proof of~(\dag) will in fact give that 
$$
R=R_n(\cP,H)\to(\cG^k,H),
$$
where the arrow notation above means that, when we colour the edges
of~$R$ with colours red and blue, either we obtain a blue induced copy
of~$H$, or else we obtain a red induced copy of \textit{every} graph
on~$k$ vertices.

%Our proof below in fact shows that~$n$ with~$n\sim t^{1000k\log q}$
%will do.
%Below, we are only concerned with large~$t$ and, consequently,
%large~$n$.  Note in particular that our inequalities below need only
%hold for large enough~$n$.

\subsection{Monochromatic subgraphs in~$R=R_n(\cP,H,\Pi)$}
\label{sec:monochro}
Throughout this section, we assume that graphs~$G$ and~$H$ as in the
statement of Lemma~\ref{lem:variant} are given.

Let us fix a projective plane~$\cP=(V,\cL)$ with~$|V|=|\cL|=n$.  Let us also
fix a family~$\Pi=(\Pi_L)_{L\in\cL}$ of $V(H)$-indexed partitions of the lines
of~$\cP$.  We may thus consider the graph~$R=R(\cP,H,\Pi)$ defined in
Section~\ref{sec:construct}.  Suppose the edges of~$R=R(\cP,H,\Pi)$ are
coloured with colours red and blue.

In Section~\ref{sec:subsub2.5.1} below, we describe a situation in
which our red-blue coloured graph~$R$ may be guaranteed to contain an
induced red copy of~$G$.  In Section~\ref{sec:subsub2.5.2}, we study a
condition that forces blue induced copies of~$H$ in~$R$.

In both sections that follow, we shall assume that~$\Pi$ is fixed.  In
particular, our results will be deterministic and not probabilistic.  For our
arguments to work, we shall impose certain hypotheses on~$\Pi$.  Later on in
the proof of~(\dag), we shall invoke Corollary~\ref{cor:co2.7} to verify that
these conditions imposed on~$\Pi$ are met with positive probability if~$\Pi$
is chosen randomly as specified in the definition of the random
graph~$R=R_n(\cP,H)$.

\subsubsection{Red induced copies of~$G$}\label{sec:subsub2.5.1}
Fix~$0<\epsilon<1/2$.  A set $S\subset V(R)$ is \textit{hereditarily
  $\epsilon$-red-rich}, or \textit{$\epsilon$-HRR} for short,
if~$|S|\ge n^{1/2+\epsilon}t^{10k}$ and if, for every disjoint pair of
sets~$A$, $B\subset S$ with~$|A|$, $|B|\geq|S|/kt^{10k}$, we have
\begin{equation}
  \label{eq:epsilonRR}
  \ered(A,B)\geq{\frac1{10t^2}}|A||B|.
\end{equation}
Here and below, $\ered(A,B)$ denotes the number of red edges
between~$A$ and~$B$.  We shall also write~$\Ered(A,B)$ for the set of
red edges between~$A$ and~$B$.  Moreover, $N(x)=N_R(x)$~denotes the
neighbourhood of the vertex~$x$ in~$R$ and~$\Nred(x)$ denotes the set
of neighbours of~$x$ in~$R$ that are joined to~$x$ by red edges.

In the beginning of Section~\ref{sec:general}, we mentioned that a notion of
`uniform richness' in red edges would appear in our arguments.  The property
of $\epsilon$-red-richness is the precise formulation of this notion.  As
inequality~(\ref{eq:epsilonRR}) may suggest, roughly speaking, $t^{-2}$~will
be the `cut-off' density in our argument: if we find a (large) set~$S$ of
vertices in our red-blue edge-coloured graph that has red-edge
density~$\Omega(t^{-2})$ (in fact, not only~$S$ but if all its large subsets
has this red-edge density), then we search for a red induced copy of~$G$
within~$S$.  On the other hand, if no such set exists, we shall seek a blue
induced copy of~$H$.

Our next lemma, Lemma~\ref{lem:l4}, states that $\epsilon$-HRR sets~$S$ do
indeed contain red induced copies of~$G$, as long as some technical conditions
are met.  These technical conditions are basically to guarantee that our
graph~$R=R_n(\cP,H,\Pi)$ satisfies a suitable pseudorandomness property
(cf.~Lemma~\ref{lem:l2}).  The underlying idea in the proof of
Lemma~\ref{lem:l4} below is a well known one, and the reader is referred to
Chv\'atal, R\"odl, Szemer\'edi, and Trotter~\cite{ChvRoSzT} and
R\"odl~\cite{rodl86} for former applications of this idea.

Finally, we observe that in later applications of Lemma~\ref{lem:l4} below, we
shall have~$\epsilon=1/10$.

\begin{lemma}\label{lem:l4}
  Let~$0<\epsilon<1/2$ be fixed, and assume~$\Pi=(\Pi_L)_{L\in\cL}$ is
  a family of $V(H)$-indexed partitions of the lines of~$\cP$ for
  which~$\Prop(\epsilon,1/30,1/80,\Pi)$ holds.  Moreover,
  suppose~$t\geq80$.  Then the graph~$R=R_n(\cP,H,\Pi)$ is such that
  every $\epsilon$-HRR set~$S\subset V(R)$ contains an induced red
  copy of~$G$.
\end{lemma}
\begin{proof}
  Observe first that, since~$\Prop(\epsilon,1/30,1/80,\Pi)$ holds,
  Lemma~\ref{lem:l2} implies that
  \begin{equation}
    \label{eq:pseudo}
    e(A,B)\sim_{1/6}\gamma|A||B|
  \end{equation}
  holds any pair of disjoint sets~$A$, $B\subset V(R)$ with~$|A|$, $|B|\geq
  n^{1/2+\epsilon}$.

  Let~$S_i\subset S$ ($1\leq i\leq k$) be~$k$ pairwise disjoint subsets
  of~$S$, each with cardinality~$|S_i|=\lfloor|S|/k\rfloor$.  Suppose
  $V(G)=\{v_1,\dots,v_k\}$.  We shall find~$s_i\in S_i$ ($1\leq i\leq
  k$) so that~$\{s_i,s_j\}\in E(R)$ if and only if~$\{v_i,v_j\}\in E(G)$ and,
  moreover, so that all such edges~$\{s_i,s_j\}$ are coloured red.
  
  Applying~(\ref{eq:pseudo}) to the pairs of sets~$(S_1,S_j)$, where~$2\leq
  j\leq k$, we may deduce that there are fewer than~$(k-1)n^{1/2+\epsilon}$
  many vertices~$s\in S_1$ such that~$|N(s)\cap S_j|>(2/3)|S_j|$ for
  some~$j=2,\dots,k$.  Furthermore, there are fewer than~$(k-1)|S|/kt^{10k}$
  vertices~$s\in S_1$ with $|\Nred(s)\cap S_j|<|S_j|/10t^2$ for
  some~$j=2,\dots,k$.  This follows since~$S$ is $\epsilon$-HRR.  Thus, since
  $$
  |S_1|>{\frac{(k-1)|S|}{kt^{10k}}}+(k-1)n^{1/2+\epsilon}, 
  $$ 
  there exist a vertex~$s_1\in S_1$ and sets~$S_\ell^{(1)}$ ($1<\ell\leq k$)
  with~$|S_\ell^{(1)}|=\lceil|S_\ell|/10t^2\rceil$ so that, for~$s\in
  S_\ell^{(1)}$, if~$\{v_1,v_\ell\}\in E(G)$ then~$\{s_1,s\}\in \Ered(R)$ and 
  if~$\{v_1,v_\ell\}\not\in E(G)$ then~$\{s_1,s\}\not\in E(R)$.  We repeat
  this procedure~$k-1$ times.

  On the $j$th step ($2\leq j\leq k$) we construct sets~$S_\ell^{(j)}$
  ($j<\ell\leq k$), each of
  cardinality~$\lceil|S_\ell|/(10t^2)^j\rceil$, and select a vertex~$s_j\in
  S_j^{(j-1)}$ such that for~$s\in S^{(j)}_\ell$ ($j<\ell\leq k$) we have that
  if~$\{v_j,v_\ell\}\in E(G)$ then $\{s_j,s\}\in\Ered(R)$ and
  if~$\{v_j,v_\ell\}\not\in E(G)$ then~$\{s_j,s\}\not\in 
  E(R)$.  The existence of such a vertex~$s_j$ follows similarly as before
  since
  $$ 
  |S_j^{(j-1)}|=\llceil\frac{|S_j|}{(10t^2)^{j-1}}\rrceil
      >\frac{(k-j)|S|}{kt^{10k}}+(k-j)n^{1/2+\epsilon}.
  $$
  The inductive procedure above constructs a red induced copy of~$G$
  in~$R$, as required.
\end{proof}

Note that the proof above in fact shows that, under the conditions
given in the lemma, an $\epsilon$-HRR set of vertices in~$R$ is
\textit{red $k$-universal}, by which we mean that it induces a red
copy of \textit{any} graph on~$k$ vertices.

\subsubsection{Blue induced copies of~$H$}\label{sec:subsub2.5.2}
We may now turn to the lemma that gives a sufficient condition for the
existence of a blue induced copy of~$H$ in~$R$.  Let us recall
that~$q=\chi(H)$ and that~$\twt=t/q$.  In the sequel, if~$s$ is a
positive integer, we shall write~$\Perm(s)$ for the set of
permutations of the set~$[s]=\{1,\dots,s\}$.

Perhaps it is worth observing that, in Lemma~\ref{lem:l3} below, the
hypothesis on the number of edges `across' the sets~$A_i$ guarantees
that the `density of red edges' across these sets is at most~$1/5t^2$.
It is this small density of red edges that will allow us to find
induced blue copies of~$H$ through an application of
Lemma~\ref{claim:cl2}.  

A comparison between Lemmas~\ref{lem:l4} and~\ref{lem:l3} suggests that,
roughly speaking, $t^{-2}$~should be a good `cut-off' density for our
arguments (cf.~the remark following inequality~(\ref{eq:epsilonRR}) concerning
this `cut-off' density.)

In the proof of Theorem~\ref{thm:variant}, we shall be concerned with
property~$\Prop(\epsilon,\delta,\eta,\Pi)$ with~$\epsilon=1/10$,
$\delta=1/30$, and~$\eta=1/80$.  However, Lemma~\ref{lem:l3} below is stated
with a weaker (larger~$\delta$ and~$\eta$) and more general
(arbitrary~$\epsilon$) hypothesis on~$\Pi$.

\begin{lemma}\label{lem:l3}
  Let~$0<\epsilon\leq1/3$ be fixed and suppose~$\Pi=(\Pi_L)_{L\in\cL}$
  is a family of $V(H)$-indexed partitions of the lines of~$\cP$.
  If~$\Prop(\epsilon,1/3,1/2,\Pi)$ holds, then~$R=R(\cP,H,\Pi)$ has
  the following property.  Let $A_1,\dots,A_q$ be pairwise disjoint
  subsets of vertices of~$R$ with~$|A_1|=\dots=|A_q|=m$,
  where~$m\geq\twt(n^{1/2+\epsilon}+1)$.  Assume moreover that 
  \begin{equation}
    \label{eq:upbdhyp}
    \sum_{1\leq i<j\leq q}\ered(A_i,A_j)
      \leq{\frac1{5t^2}}\sum_{1\leq i<j\leq q}|A_i||A_j|
%     =\frac1{5q^2\twt^2}\sum_{1\leq i<j\leq q}|A_i||A_j|
      =\frac1{5t^2}\binom q2m^2.
  \end{equation}
  Then there exist~$v_i\in\bigcup_{1\leq j\leq q}A_j$ $(1\leq i\leq t)$
  that induce a blue copy of~$H$ in~$R$.  
\end{lemma}
\begin{proof}  Recall we have a fixed proper
  vertex colouring~$V(H)=\bigcup_{1\leq i\leq q}V_i$ of~$H$
  with~$|V_1|=\dots=|V_q|=w=t/q$.  We write~$V_i=\{v_{ij}\:1\leq
  j\leq\twt\}$ ($1\leq i\leq q$).  Let~$L$ be a line of our projective
  plane.  The labelling~$v_{ij}$ of the vertices of~$H$ gives a
  natural labelling of the members~$L_v$ of the
  partition~$L=\bigcup_vL_v$ of~$L$ in~$\Pi$.  Namely, we let the
  partition classes of~$L$ be denoted by~$L_{ij}$ ($1\leq i\leq q$,
  $1\leq j\leq\twt$) in the natural way.  Finally, for each~$1\leq
  i\leq q$, choose~$\twt$ pairwise disjoint subsets~$A_{ij}\subset
  A_i$ ($1\leq j\leq\twt$) with~$|A_{ij}|=\lfloor m/\twt\rfloor\geq
  n^{1/2+\epsilon}$ for each~$j$.

  Note that a line~$L$ is $(A_{ij},\delta,\Pi)$-normal if we have
  \begin{equation}
    \label{eq:prop}
    |L_{i'j'}\cap A_{ij}|
      \sim_\delta\frac{|A_{ij}|}{t\sqrt n}
      =\frac{\lfloor m/\twt\rfloor}{q\twt\sqrt n}
  \end{equation}
  for all~$1\leq i'\leq q$, $1\leq j'\leq\twt$.  Let~$\delta=1/3$.  In
  this proof, we shall make use of the lines~$L$ that are
  $(A_{ij},\delta,\Pi)$-normal for \textit{all} the $t$~sets~$A_{ij}$
  ($1\leq i\leq q$, $1\leq j\leq\twt$).  Write~$\cL_\delta$ for the
  set of all such lines.  Then, clearly, we have
  \begin{equation*}
%   \label{eq:cLdelta}
    \cL_\delta=\cL(\bfA,\delta,\Pi), 
  \end{equation*}
  where~$\bfA=(A_{ij})_{1\leq i\leq q,1\leq j\leq\twt}$
  (cf.~(\ref{eq:cLbfXdeltaPi})).  Since we are assuming that
  property~$\Prop(\epsilon,1/3,1/2,\Pi)$ holds, we know that
  \begin{equation}
    \label{eq:cLdeltalb}
    |\cL_\delta|\geq n/2.
  \end{equation}
  
  We now consider $(q+1)$-tuples of
  permutations~$\bsigma=(\sigma_0;\sigma_1,\dots,\sigma_q)$,
  where~$\sigma_0\in\Perm(q)$ and~$\sigma_i\in\Perm(\twt)$ ($1\leq
  i\leq q$).  In the sequel, if~$(i,j)\in[q]\times[\twt]$, we
  write~$\bsigma(i,j)$ for the pair~$(a,b)\in[q]\times[\twt]$
  where~$a=\sigma_0(i)$, and~$b=\sigma_a(j)=\sigma_{\sigma_0(i)}(j)$.
  
  Now suppose~$L\in\cL_\delta$.  Define~$f(L,\bsigma)$ to be the
  number of red edges across the sets~$A_{ij}\cap L_{\bsigma(i,j)}$,
  where a red edge is counted only if its endvertices belong to two
  such sets with distinct~$i$.

  We now average over~$L\in\cL_\delta$ and~$\bsigma$.  We have
  \begin{equation}
    \label{eq:ave}
    \sum_{L\in\cL_\delta}\sum_{\bsigma}f(L,\bsigma)
      \leq\sum_{L\in\cL}\sum_{\bsigma}f(L,\bsigma).
  \end{equation}
  The sum on the right-hand side of~(\ref{eq:ave}) above is, however,
  $$
  (q-2)!(\twt-1)!^2\twt!^{q-2}
  $$ 
  times the number of red edges across the~$A_i$ (\textit{i.e.}, having
  endvertices in distinct~$A_i$).  To see this, let us fix one such edge~$e$;
  say, $e=xy$ and~$x\in A_{ij}$ and~$y\in A_{i'j'}$.  Note for later reference
  that~$i\neq i'$.  The vertices~$x$ and~$y$ determine a unique
  line~$L\in\cL$.  It now suffices to notice that the values of~$i\neq i'$,
  $j$, and~$j'$ tells us that, out of all the $q!\twt!^q$ possibilities,
  exactly $(q-2)!(\twt-1)!^2\twt!^{q-2}$
  vectors~$\bsigma=(\sigma_0;\sigma_1,\dots,\sigma_q)$ are such that
  $$
  x\in A_{ij}\cap L_{\bsigma(i,j)}\quad
      \text{ and }\quad y\in A_{i'j'}\cap L_{\bsigma(i',j')}.
  $$
  Therefore, we may indeed deduce that the left-hand side
  of~(\ref{eq:ave}) above is, by~(\ref{eq:upbdhyp}), at most
  \begin{multline*}
    (q-2)!(\twt-1)!^2\twt!^{q-2}{\frac1{5q^2\twt^2}}
                        \sum_{1\leq i<j\leq q}|A_i||A_j|\\
       \leq(q-2)!{\frac{\twt!^q}{5q^2\twt^4}}{\binom q2}m^2
                     ={\frac{q!\twt!^q}{10q^2\twt^4}}m^2.
  \end{multline*}
  Since~(\ref{eq:cLdeltalb}) holds and there are~$q!\twt!^q$
  many~$\bsigma$, there exists a pair~$(L,\bsigma)$
  with~$L\in\cL_\delta$ satisfying  
  \begin{equation}
    \label{eq:fLsigma}
    f(L,\bsigma)\leq{\frac{m^2}{5nq^2\twt^4}}.
  \end{equation}
  Fix such a pair~$(L,\bsigma)$.  Recall~(\ref{eq:prop}), and pick a
  set~$X_{ij}\subset A_{ij}\cap L_{\bsigma(i,j)}$
  with~$|X_{ij}|=s=\lceil(3/4)m/q\twt^2\sqrt n\rceil$ for each~$1\leq
  i\leq q$, $1\leq j\leq\twt$.  Note that the~$t$ sets~$X_{ij}$ induce
  in~$R$ a copy of~$H_s$, the $s$-fold blow-up of~$H$.  We
  have~$m\leq(4/3)sq\twt^2\sqrt n$.  Hence, we have that the number of
  red edges in this copy of~$H_s$ is at most~$f(L,\bsigma)<s^2$,
  by~(\ref{eq:fLsigma}).  It now suffices to apply
  Lemma~\ref{claim:cl2} to~$H_s$ to deduce that there is an induced
  blue copy of~$H$ in~$R$, as required.
\end{proof}

\subsection{The proof of Theorem~\ref{thm:variant}}
\label{sec:proof-variant}
As observed in Section~\ref{sec:main-lemma}, it suffices to prove
Lemma~\ref{lem:variant} to prove Theorem~\ref{thm:variant}.
Lemma~\ref{lem:variant} is, however, a consequence of assertion~(\dag)
in Section~\ref{sec:main-lemma}, and hence we are left with proving
that assertion.

\begin{proof}[Proof of~{\rm(\dag)}]
  We fix~$\epsilon=1/10$ and pick a prime~$p$ such that~$n=p^2+p+1$
  satisfies
  $$
  t^{Ck\log q}\leq n\leq4t^{Ck\log q}, 
  $$
  where~$C=1000$.  The existence of such a prime~$p$ follows easily
  from Chebyshev's theorem.  Observe now that
  \begin{equation}
    \label{eq:tconds}
    \log n\ll t\ll n^{\epsilon/2}.
  \end{equation}
  Indeed, the lower bound on~$t$ follows since~$t\geq k^2$, and the
  upper bound follows by the choice of~$C$.  Let us now observe that, 
  quite crudely, 
  \begin{equation}
    \label{eq:t-cond}
    n^{0.4}\geq t^{1+100k(\log_2q+1)}.
  \end{equation}
  Moreover, note that there is an absolute constant~$t_0$ such that if~$t\geq
  t_0$, then~$n\geq n_0(1/10,1/30,1/80,t)$, where~$n_0$ is as given in
  Corollary~\ref{cor:co2.7}.  Clearly, we may assume that~$t_0\geq80$.  We
  shall show that this choice of~$t_0$ will do in assertion~(\dag).
  
  Suppose graphs~$G$ and~$H$ as in~(\dag) are given, and suppose
  that~$t\geq t_0$.  Let~$\cP=(V,\cL)$ be a projective plane of
  order~$p$.  Then~$|V|=|\cL|=n=p^2+p+1$.  Recall~(\ref{eq:tconds}),
  and invoke Corollary~\ref{cor:co2.7} to see that there is a family
  of $V(H)$-indexed partitions~$\Pi=(\Pi_L)_{L\in\cL}$ of the lines
  of~$\cP$ for which
  property~$\Prop(\epsilon,1/30,1/80,\Pi)=\Prop(1/10,1/30,1/80,\Pi)$
  holds.  Fix such a~$\Pi$, and let~$R=R_n(\cP,H,\Pi)$.  We claim
  that~$R\to(G,H)$.  Clearly, this will finish the proof of~(\dag).
  
  To prove our claim, we invoke Lemmas~\ref{lem:l4} and~\ref{lem:l3}.
  Since~$t\geq t_0\geq80$ and property~$\Prop(1/10,1/30,1/80,\Pi)$
  holds, according to Lemma~\ref{lem:l4}, we may assume that~$V(R)$
  contains no $\epsilon$-HRR subset.  Indeed, according to that lemma,
  if there is an $\epsilon$-HRR set of vertices in~$R$, we must have a
  red induced copy of~$G$ in~$R$.  In the remainder of the proof, we
  show that the existence of no such $\epsilon$-HRR subset of vertices
  implies the existence of sets~$A_i$ ($1\leq i\leq q$) as required in
  Lemma~\ref{lem:l3}.  An application of that lemma will then give us
  a blue induced copy of~$H$, completing the proof of~(\dag).
  
  To carry out the plan above, we shall need the following technical lemma.
  Let~$\{0,1\}^\ell$ denote the set of all $0$--$1$~strings of length~$\ell$.
  
  \assertion(\ddag) Let~$\ell=\lceil\log_2q\rceil$.  There are~$2^\ell$
  pairwise disjoint sets~$X_I\subset V(R)$ $(I\in\{0,1\}^\ell)$, each of
  cardinality~$m=\lceil n/t^{100\ell k}\rceil$, satisfying
  \begin{equation}
    \label{eq:rTotBd}
    \sumell\ell{I}J\ered(X_I,X_J)
       <\(\frac{1}{1-kt^{-90k}}\)^{2(\ell-1)}
         \frac{1}{10t^2}\sumell\ell{I}J|X_I||X_J|,
  \end{equation}
  where~$\sumell\ell{I}J$ indicates sum over all~$I$, $J\in\{0,1\}^\ell$
  with~$I\neq J$.
  \endassertion
  
  We postpone the proof of~(\ddag), and carry on with the proof of~(\dag).
  Assertion~(\ddag) gives us~$2^\ell$ sets~$X_I$ satisfying~(\ref{eq:rTotBd}),
  where~$\ell=\lceil\log_2q\rceil$.  In particular, we have~$2^\ell\geq q$.  A
  simple averaging argument now gives that some~$q$ of the sets~$X_I$,
  say~$A_i$ ($1\leq i\leq q$), are such that the number of red edges across
  these~$q$ sets is at most the quantity given in~(\ref{eq:upbdhyp}), as
  required in Lemma~\ref{lem:l3}.  Recall that
  property~$\Prop(1/10,1/30,1/80,\Pi)$ holds.  Moreover, note that the
  sets~$A_i$ have cardinality~$m=\lceil n/t^{100\ell
    k}\rceil\geq\twt(n^{0.6}+1)$.  It follows from Lemma~\ref{lem:l3} that
  there must be a blue induced copy in~$R$.  This completes the proof of the
  claim that~$R\to(G,H)$, and the proof of~(\dag) will be complete once we
  establish~(\ddag).
\end{proof}

\begin{proof}[Proof of~{\rm(\ddag)}]
  We prove the existence of the sets~$X_I$ ($\ell\in\{0,1\}^\ell$) by
  induction on~$\ell$.  This is simple for~$\ell=1$: since~$V(R)$ is not
  $\epsilon$-HRR, there are sets~$X'_0$, $X'_1\subset V(R)$ with~$|X'_i|\geq
  n/kt^{10k}$ ($i\in\{0,1\}$) so that
  \begin{equation}
    \label{eq:rUpBd}
    \ered(X'_0,X'_1)<{\frac1{10t^2}}|X_0'||X_1'|.
  \end{equation}
  An easy averaging argument shows that there are in fact $X_0\subset X'_0$,
  $X_1\subset X'_1$ with $|X_0|=|X_1|=\lceil n/t^{100k}\rceil<n/kt^{10k}$ such
  that~(\ref{eq:rUpBd}) remains true if~$X'_i$ is replaced~$X_i$
  ($i\in\{0,1\}$).  We now turn to the induction step. 
  
  Assume that, for some~$1\leq\ell<\log_2q=\log_2\chi(H)$, we have
  constructed~$2^\ell$ sets~$X_J$ ($J\in\{0,1\}^\ell$)
  with~$|X_J|=\lceil n/t^{100\ell k}\rceil$ such that
  inequality~(\ref{eq:rTotBd}) holds.  We checked above that we do
  have this situation for~$\ell=1$.  Our aim now is to show that there
  exist sets~$X_I$ ($I\in\{0,1\}^{\ell+1}$) satisfying
  condition~(\ref{eq:rTotBd}) with~$\ell$ replaced by~$\ell+1$ and
  with~$|X_I|=\lceil n/t^{100(\ell+1)k}\rceil$ for all~$I$.
  
  Let 
  $$
  u=\llfloor\frac12(t^{100k}-kt^{10k})\rrfloor.
  $$
  We now prove the following assertion.
  
  \assertion(\ddag\ddag)  Each~$X_J$ $(J\in\{0,1\}^\ell)$
  contains~$u+1$ pairs of disjoint sets~$Y_{J,2i}$,
  $Y_{J,2i+1}\subseteq X_J$ $(0\leq i\leq u)$ such that 
  \begin{equation}
    \label{eq:cond1}
    |Y_{J,2i}|=|Y_{J,2i+1}|=\llceil\frac n{t^{100(\ell+1)k}}\rrceil
  \end{equation}
  and 
  \begin{equation}
    \label{eq:cond2}
    \ered(Y_{J,2i},Y_{J,2i+1})<\frac1{10t^2}|Y_{J,2i}||Y_{J,2i+1}|.
  \end{equation}
  \endassertion
  
  Let us prove~(\ddag\ddag).  We fix~$J\in\{0,1\}^\ell$ and construct
  the~$Y_{J,j}$ ($0\leq j\leq2u+1$) by induction, using the fact that
  no subset of~$X_J$ is $\epsilon$-HRR.
  
  Since each~$X_J$ has cardinality larger
  than~$n^{1/2+\epsilon}t^{10k}$ but is not $\epsilon$-HRR, we can
  find set~$Y_{J,0}$, $Y_{J,1}$ satisfying~(\ref{eq:cond1}) and such
  that~(\ref{eq:cond2}) holds.  We now proceed inductively.  Suppose
  the sets~$Y_{J,2(i-1)}$, $Y_{J,2(i-1)+1}$ ($1\leq i\leq u$) have
  been found.  Put~$Z_J=X_J\setminus\bigcup_{0\leq j\leq2u-1}Y_{J,j}$.
  Observe that
  $$
  |Z_J|=|X_J|-\sum_{0\leq j\leq2u-1}|Y_{J,j}|
            \geq kt^{10k}\frac n{2t^{100k(\ell+1)}}, 
  $$
  where the last inequality is in fact quite crude.  Since~$\ell<\log_2q$
  and~(\ref{eq:t-cond}) holds, we have
  $$
  kt^{10k}\frac{n}{2t^{100k(\ell+1)}} 
   \ge kt^{10k}\frac{n}{2t^{100k(\log_2q+1)}}\ge n^{0.6}t^{10k}
   =n^{1/2+\epsilon}t^{10k}.
  $$
  Hence, the fact that~$Z_J$ is not $\epsilon$-HRR implies that there
  are two sets~$Y_{J,2i}$, $Y_{J,2i+1}$ satisfying~(\ref{eq:cond1})
  and~(\ref{eq:cond2}).  The existence of the sets~$Y_{J,j}$
  ($0\leq j\leq2u+1$) follows by induction.  Since~$J$ was arbitrary,
  assertion~(\ddag\ddag) is proved.

  Let us now proceed with the proof of~(\ddag).  For
  all~$J\in\{0,1\}^\ell$, set 
  $$
  Y_J=\bigcup_{i=0}^{2u+1}Y_{J,i}.
  $$
  Then we have that
  \begin{multline*}
  |Y_J|\ge2(u+1)\llceil\frac{n}{t^{100(\ell+1)k}}\rrceil\\
      \geq(t^{100k}-kt^{10k})\llceil\frac{n}{t^{100(\ell+1)k}}\rrceil
       \geq\(1-\frac{k}{t^{90k}}\)|X_J|.
  \end{multline*}
  We may therefore infer from~(\ref{eq:rTotBd}) that
  \begin{multline*}
     \sumell\ell{I}J\ered(Y_I,Y_J)<\sumell\ell{I}J\ered(X_I,X_J)\\
      \le\(\frac{1}{1-kt^{-90k}}\)^{2(\ell-1)}
            \frac{1}{10t^2}\(\frac{1}{1-kt^{-90k}}\)^2
             \sumell\ell{I}J|Y_I||Y_J|.
  \end{multline*}
  Now note that
  $$
  \ered(Y_I,Y_J)
    =\sum_{i,j}\ered(Y_{I,2i}\cup Y_{I,2i+1},Y_{J,2j}\cup Y_{J,2j+1}),  
  $$
  where the sum is taken over~$0\le i\le u$ and~$0\le j\le u$.  It follows
  from an averaging argument that, for each~$I\in\{0,1\}^\ell$, there
  exists~$r_I$ ($0\le r_I\le u$) so that 
  \begin{multline*}
  \sumell\ell{I}J\ered(Y_{I,2r_I}
        \cup Y_{I,2r_I+1},Y_{J,2r_J}\cup Y_{J,2r_J+1})\\
    <\(\frac{1}{1-kt^{-90k}}\)^{2\ell}
      \frac{1}{10t^2}\sumell\ell{I}J|Y_{I,2r_I}
       \cup Y_{I,2r_I+1}||Y_{J,2r_J}\cup Y_{J,2r_J+1}|.
  \end{multline*}
  For each $I\in\{0,1\}^\ell$, set~$X_{I,0}=Y_{I,2r_I}$,
  $X_{I,1}=Y_{I,2r_I+1}$.  In this way we get a collection
  of~$2^{\ell+1}$ sets $X_L$ ($L\in\{0,1\}^{\ell+1}$)
  with~$|X_L|=\lceil n/t^{100(\ell+1)k}\rceil$ for all~$L$ and such
  that  
  $$
  \sumell{\ell+1}L{L'}\ered(X_L,X_{L'})
    <\(\frac{1}{1-kt^{-90k}}\)^{2\ell}
         \frac{1}{10t^2}\sumell{\ell+1}L{L'}|X_L||X_{L'}|.
  $$
  This finishes the induction step and~(\ddag) is proved. 
\end{proof}  

\section{Erd\H os--Hajnal Simple Graphs}
\label{sec:simple}
Our aim in this section is to prove Theorem~\ref{thm:EHsimple}.  We
shall again use the random graphs~$R=R_n(\cP,H)$ introduced in
Section~\ref{sec:construct}.

We start by observing that we may assume that the
edge-density~$\gamma=e(H){\binom t2}^{-1}$ of the graph~$H$ in the
statement of Theorem~\ref{thm:EHsimple}
satisfies~$3/7\leq\gamma\leq4/7$.  We shall make use of this
assumption towards the end of this section.  Furthermore, we may
assume that~$t$ is larger than some suitably large constant so that
the inequalities below hold.

The proof of Theorem~\ref{thm:EHsimple} will be by induction on the
number of vertices of~$G$.  However, to make the induction work, we
shall need to boost up the claim in that theorem.  

\subsection{A stronger version of Theorem~\ref{thm:EHsimple}}
\label{sec:boostedup}
For graphs~$\Gamma$, $G$, and~$H$, and a real number~$M>0$, let us
write~$\Gamma\marrows{M}(G,H)$ if in any red-blue colouring of the
edges of~$\Gamma$, there are either at least~$M$ red induced copies
of~$G$, or else there is at least one blue induced copy of~$H$.  

Suppose a projective plane~$\cP=(V,\cL)$ with~$|\cL|=|V|=n$ and a
$t$-vertex graph~$H$ are fixed.  Consider the
graph~$R=R_n(\cP,H,\Pi)$, where, as usual, $\Pi=(\Pi_L)_{L\in\cL}$ is
some family of $V(H)$-indexed partitions of the lines~$L$ of~$\cP$.
Let a simple graph~$G$ on $k$~vertices be fixed.  We shall show below
that, if~$n\geq t^f$ for some large enough~$f=f(k)$ and
property~$\Prop(\epsilon,\delta,\eta,\Pi)$ holds for small
enough~$\epsilon$, $\delta$, and~$\eta>0$, then
$$
R\marrows{M}(G,H),
$$
where~$M=n^{(1-\rho)k}$, for any constant~$\rho>0$ that is fixed in
advance.  It turns out that the assertion above is still not enough to
make the induction work.  Indeed, we need a `local' version of the
assertion above.  In the result below, as customary, if~$X\subset V$,
we write~$R[X]$ for the subgraph of~$R$ induced by~$X$.

\begin{lemma}\label{lem:EHsimpleS}
  Let constants~$\epsilon$ and~$\rho>0$ and a $k$-vertex simple
  graph~$G$ be given.  Then there exist
  constants~$f=f(\epsilon,\rho,G)$
  and~$\tepsilon=\tepsilon(\epsilon,\rho,G)>0$ for which the following
  holds.  Let a $t$-vertex graph~$H$ be given, where~$t\geq80$, and
  suppose~$\cP=(V,\cL)$ is a projective plane on~$n\geq t^f$ points.
  Consider the graph~$R=R_n(\cP,H,\Pi)$, where~$\Pi=(\Pi_L)_{L\in\cL}$
  is such that~$\Prop(\tepsilon,1/30,1/80,\Pi)$ holds.  Then, for
  all~$X\subset V$ with~$|X|\geq n^{1/2+\epsilon}$, we have 
  \begin{equation}
    \label{eq:localmarrowsM}
    R[X]\marrows{M}(G,H), 
  \end{equation}
  where~$M=|X|^{(1-\rho)k}$.
\end{lemma}
\begin{proof}
  The proof will be by induction on~$k=|V(G)|$.  If~$k=1$, there is
  nothing to do, as~(\ref{eq:localmarrowsM}) holds trivially in this
  case for any~$\rho>0$.  Thus, let us assume that~$k\geq2$ and that
  our lemma holds for smaller values of~$k$.  Let~$\epsilon$,
  $\rho>0$, and a $k$-vertex simple graph~$G$ be given.
  Then~$G=G_1\dcup G_2$ or else~$G=G_1\vee G_2$ for a pair of
  graphs~$(G_1,G_2)$ with~$G_i$ of order~$k_i<k$ ($i=1$, $2$).  Let us
  consider the case in which~$G$ is the join of the graphs~$G_1$
  and~$G_2$.  The other case is similar and a little simpler.  We
  shall make a couple of comments about that case later on.
  
  To find the constants~$f$ and~$\tepsilon$ as required in the lemma, we need
  to make a few numerical considerations.  Let~$\eta=1/2+\epsilon$.  

  \assertion(\dag\dag) There exist constants~$\eta'$, $\eta''$,
  and~$\trho$ such that~$1/2<\eta''<\eta'<\eta$, $0<\trho<\rho$, and 
  \begin{enumerate}
  \item[(\textit{i})]
    $\eta''<\eta'+\eta'(1-\trho)k_2-\eta k_2$, 
  \item[(\textit{ii})]
    $\eta''(1-\trho)k_1+\eta'(1-\trho)k_2+\eta'-\eta>\eta(1-\rho)k$.
  \end{enumerate}
  \endassertion

  We postpone the proof of~(\dag\dag), and carry on with the proof of
  Lemma~\ref{lem:EHsimpleS}.
  Fix~$\eta'$, $\eta''$, and~$\trho$ as in the assertion above.
  Let~$\eta'=1/2+\epsilon'$ and~$\eta''=1/2+\epsilon''$.  Clearly,
  $\epsilon'$, $\epsilon''>0$.  Let us apply the induction hypothesis
  to the triples~$(\epsilon'',\trho,G_1)$ and~$(\epsilon',\trho,G_2)$.
  Let~$f(\epsilon'',\trho,G_1)$, $f(\epsilon',\trho,G_2)$,
  $\tepsilon(\epsilon'',\trho,G_1)$,
  and~$\tepsilon(\epsilon',\trho,G_2)$ be the constants whose
  existence is guaranteed by the induction hypothesis.   Put
  \begin{equation}
    \label{eq:fdef}
    f=f(\epsilon,\rho,G)
     =\max\left\{\frac2{\epsilon-\epsilon'},
                  f(\epsilon'',\trho,G_1),f(\epsilon',\trho,G_2)\right\}
  \end{equation}
  and
  \begin{equation}
    \label{eq:tepsdef}
    \tepsilon=\tepsilon(\epsilon,\rho,G)
     =\min\{\epsilon,\tepsilon(\epsilon'',\trho,G_1),
                     \tepsilon(\epsilon',\trho,G_2)\}.
  \end{equation}
  We claim that the above choice for~$f$ and~$\tepsilon$ will do.  To
  prove our claim, let a $t$-vertex graph~$H$ be given,
  where~$t\geq80$, let~$\cP=(V,\cL)$ be a projective plane on~$n\geq
  t^f$ points, and suppose~$\Pi=(\Pi_L)_{L\in\cL}$
  satisfies~$\Prop(\tepsilon,1/30,1/80,\Pi)$.  Moreover, fix~$X\subset
  V$ with~$|X|\geq n^\eta=n^{1/2+\epsilon}$.  We shall now prove
  that~(\ref{eq:localmarrowsM}) holds for~$M=|X|^{(1-\rho)k}$.  A
  simple averaging argument shows that it suffices to consider the
  case in which~$|X|=n^\eta=n^{1/2+\epsilon}$.  (For simplicity, in
  this proof we ignore ceiling and floor functions.)
  
  Let~$R[X]$ have its edges coloured red and blue, and suppose that
  there is no blue induced of~$H$ in~$R[X]$.  We must find at
  least~$M$ red induced copies of~$G$ in~$R[X]$.
  Put~$\cL(X,1,\Pi)=\{L\in\cL\:\text{$L$ is $(X,1,\Pi)$-normal}\}$.
  Then, since~$\Prop(\epsilon,1,1/2,\Pi)$ clearly holds,
  we have
  \begin{equation}
    \label{eq:cLX1Pi}
    |\cL(X,1,\Pi)|\geq n/2.
  \end{equation}
  Let~$s=|X|/2t\sqrt n$.  Each line~$L$ in~$\cL(X,1,\Pi)$ induces an
  $s$-fold blow-up~$H_s$ of~$s$.  Thus, by Lemma~\ref{claim:cl2}, each
  such line must induce at least~$s^2$ red edges.
  Using~(\ref{eq:cLX1Pi}), we see that~$R[X]$ must contain at least
  $$
  \frac12ns^2\geq\frac{|X|^2}{8t^2}
  $$
  red edges.  Write~$\dXr(x)$ for the number of red edges in~$R[X]$
  that are incident to the vertex~$x\in X$.  A simple argument shows
  that the number of vertices~$x\in X$ such that~$\dXr(x)\geq|X|/8t^2$
  is at least~$|X|/8t^2$.  Let us fix one such vertex~$x$, and let us
  look at the set~$X'=\Nred(x)\cap X$ of vertices in~$X$ that are
  joined to~$x$ by red edges.
  
  Since~$f\geq2/(\epsilon-\epsilon')$, we have
  that~$|X'|\geq|X|/8t^2\geq n^{\eta'}$.  Since~$f\geq
  f(\epsilon',\trho,G_2)$
  and~$\tepsilon\geq\tepsilon(\epsilon',\trho,G_2)$, we may deduce
  that~$R[X']$ induces at least $n^{(1-\trho)\eta'k_2}$ red copies
  of~$G_2$.  Thus, the total number of red induced copies of~$K^1\vee
  G_2$ within~$R[X]$ is at least
  $$
  \frac{|X|}{8t^2}n^{(1-\trho)\eta'k_2}
   \geq n^{\eta'+(1-\trho)\eta'k_2}.
  $$
  Let us say that a red induced copy of~$G_2$ in~$R[X]$ is
  \textit{good} if it belongs to at least~$n^{\eta''}$ red induced
  copies of~$K^1\vee G_2$ in~$R[X]$.  Again by a simple argument,
  using inequality~(\textit{ii}) above, we may deduce that we have at
  least
  \begin{equation}
    \label{eq:goodG2}
    \frac12n^{(1-\trho)\eta'k_2+\eta'-\eta}  
  \end{equation}
  good red induced copies of~$G_2$ in~$R[X]$.  Fix one such good copy,
  and let us look at the set~$X''\subset X$ of vertices~$x''$ that,
  together with our good copy of~$G_2$, induce a red~$K^1\vee G_2$.
  We have~$|X''|\geq n^{\eta''}$.  Since~$f\geq
  f(\epsilon'',\trho,G_1)$
  and~$\tepsilon\geq\tepsilon(\epsilon'',\trho,G_1)$, we may deduce
  that~$R[X'']$ contains at least~$n^{(1-\trho)\eta''k_1}$ red induced
  copies of~$G_1$.  Thus, our good copy of~$G_2$ in~$R[X]$ belongs to
  at least~$n^{(1-\trho)\eta''k_1}$ red induced copies of~$G$.  Taking
  into account that the number of such good copies of~$G_2$ in~$R[X]$
  is at least as large as the quantity in~(\ref{eq:goodG2}), we deduce
  that the number of red induced copies of~$G$ in~$R[X]$ is at least
  $$
  \frac12n^{(1-\trho)\eta''k_1+(1-\trho)\eta'k_2+\eta'-\eta}.
  $$
  Recalling~(\textit{i}), we see that this quantity is no smaller
  than~$n^{(1-\rho)k\eta}$.  This completes the induction step in the
  case in which~$G=G_1\vee G_2$.
  
  Let us now briefly look at the case in which~$G=G_1\dcup G_2$.  The
  argument here is similar, except that we have to make use of the
  fact that~$R[X]$ contains no pair~$(A,B)$ of fairly large disjoint
  sets with~$e(A,B)>(2/3)|A||B|$.  This follows since~$\gamma\leq4/7$,
  and inequality~(\ref{eq:lem:l2}) holds with~$\delta=1/6$ for
  any~$A$, $B\subset X$ with~$|A|$, $|B|\geq n^{1/2+\epsilon}$,
  since~$\Prop(\epsilon,1/30,1/80,\Pi)$ holds.  We omit the details.
\end{proof}

It now remains to prove~(\dag\dag).

\begin{proof}[Proof of~{\rm(\dag\dag)}]
  First we choose~$\eta''$ such that
  \begin{equation}
    \label{eq:etapp}
    \eta>\eta''>1/2
  \end{equation}
  and~$\eta''k_1>\eta k_1-\rho\eta k$. This second inequality is equivalent to
  \begin{equation}
    \label{eq:etapp2}
    \eta''k_1+\eta k_2>\eta k(1-\rho).
  \end{equation}
  Inequalities~(\ref{eq:etapp}) and~(\ref{eq:etapp2}) above imply that it is
  possible to choose an~$\eta'$ close enough to~$\eta$, with
  $\eta''<\eta'<\eta$, ensuring that
  \begin{equation}
    \label{eq:etap}
    (\eta'-\eta)k_2+\eta'>\eta''
  \end{equation}
  and that
  \begin{equation}
    \label{eq:etap2}
    \eta''k_1+\eta'k_2+\eta'-\eta>\eta k(1-\rho).
  \end{equation}
  Comparing~(\ref{eq:etap}) and~(\ref{eq:etap2}) with~(\textit{i})
  and~(\textit{ii}) in~(\dag\dag), we easily see that it is now possible to
  choose~$0<\trho<\rho$ close enough to~$0$ to guarantee~(\textit{i})
  and~(\textit{ii}).
\end{proof}

Write~$\cS^k$ for the family of simple graphs on~$k$ points.  In fact,
the proof of Lemma~\ref{lem:EHsimpleS} given above gives that  
$$
R=R_n(\cP,H,\Pi)\to(\cS^k,H), 
$$
that is, in any red-blue edge colouring of~$R$, we either have a
blue induced copy of~$H$, or else we have a red induced copy of
\textit{every} simple graph on~$k$ vertices.

Corollary~\ref{cor:co2.7} and Lemma~\ref{lem:EHsimpleS} imply
Theorem~\ref{thm:EHsimple}.  

\section{Small Trees versus General Graphs}
\label{sec:trees}
Our aim in this section is to prove Theorem~\ref{thm:trees}.  Let a
graph~$H$ of order~$t$ be fixed, and let~$\cP=(V,\cL)$ be a projective
plane with~$|V|=|\cL|=n$.  Let an integer~$k\geq2$ be given.  In this
section, we consider a random graph~$R'=R'_n(\cP,H,k)$ that is better
suited for the purposes of this section.  Indeed, to be able to prove
inequality~(\ref{eq:trees}), we must certainly consider graphs that
contain large induced trees, and hence we are better off by
considering sparser versions of the random graph~$R=R_n(\cP,H)$ that
we have considered elsewhere in this paper.  

\subsection{The construction of~$R'=R'_n(\cP,H,k)$}
\label{sec:constructT}
Let~$b=200$.  Put
\begin{equation}
  \label{eq:q-def}
  q=bk\frac{\log(kt^2)}{\log\log\log(kt^2)}.  
\end{equation}
(For simplicity, we shall ignore floor and ceiling functions in
this section.)  Suppose~$\cP=(V,\cL)$ is such that $n=|V|$
satisfies 
\begin{equation}
  \label{eq:n-cond}
  k^2t^4\(\frac{\log(kt^2)}{\log\log\log(kt^2)}\)^2
    \leq n
    \leq4k^2t^4\(\frac{\log(kt^2)}{\log\log\log(kt^2)}\)^2.
\end{equation}
Let~$L\in\cL$ be a line of~$\cP$.  Randomly choose $q$~pairwise
disjoint subsets~$W_1,\dots,W_q\subset L$ of~$L$, all of
cardinality~$t$.  Note that this is possible since~$tq\leq r+1$ holds
for large enough~$t$.  Now, randomly insert $q$~copies of~$H$ in~$L$
using these~$W_i$ as the vertex sets of these copies.  Repeat this
procedure for all the lines~$L\in\cL$ of~$\cP$, making all the random
choices independently.  The resulting random graph is
our~$R'=R'_n(\cP,H,k)$.

Let us remark that the copies of~$H$ in~$R'=R'_n(\cP,H,k)$ are in fact
pairwise edge-disjoint.  This will not, however, prevent us from proving an
edge-Ramsey result.     

\begin{lemma}\label{lem:trees-Random}
  There exist absolute constants~$k_0$ and~$t_0$ for which the
  following holds.  Let~$H$ be a graph of order~$t\geq t_0$, and
  consider~$R'=R'_n(\cP,H,k)$ for~$k\geq k_0$.  Then with positive
  probability we have that
  \begin{equation}
    \label{eq:trees-Random}
    R'=R'_n(\cP,H,k)\to(T,H)
  \end{equation}
  for any tree~$T$ of order~$k$.
\end{lemma}

Clearly, Lemma~\ref{lem:trees-Random} above implies
Theorem~\ref{thm:trees}.  In the rest of Section~\ref{sec:trees}, we
give a proof of Lemma~\ref{lem:trees-Random}.  Let us mention that,
similarly to what happened in previous sections, our proof will in
fact give a `universal' version of~(\ref{eq:trees-Random}).  Namely,
one sees from the proof below that~$T$ in~(\ref{eq:trees-Random}) may
be replaced by~$\cT^k$, the family of all trees on~$k$ points,
\textit{i.e.}, if no blue induced copy of~$H$ is found in a red-blue
edge-coloured~$R'$, then \textit{all} trees in~$\cT^k$ must be present
in~$R'$ as red induced subgraphs.

\subsection{A technical lemma on~$R'=R'_n(\cP,H,k)$}
\label{sec:tech-lemma}
Let a graph~$H$ and a projective plane~$\cP$ as in the previous section be
fixed.  The integer~$k$ is also fixed throughout this section.  Consider the
random graph~$R'=R'_n(\cP,H,k)$, and let~$x$, $y\in V(R')$ be two distinct
vertices of~$R'$.  The common neighbourhood~$N(x)\cap N(y)$ of the
vertices~$x$ and~$y$ in~$R'$ may be `unexpectedly large' (with respect to the
edge-density of~$R'$).  Indeed, this may happen because~$x$ and~$y$ may belong
to one of the copies of~$H$ that we embed in~$R'$.  However, our technical
lemma below asserts that the number of common neighbours of~$x$ and~$y$ that
do \textit{not} belong to the line~$L=L(x,y)\in\cL$ determined by~$x$ and~$y$
is fairly small.

Let us say that~$x$ and~$y$ form a \textit{normal} pair in~$R'$ if 
$$
\big|(N(x)\cap N(y))\setminus L(x,y)\big|
  \leq\frac{30\log n}{\log\log\log n}.
$$

\begin{lemma}\label{lem:common-nbrs}
  Let~$R'=R'_n(\cP,H,k)$ be as above.  Then, with probability
  approaching~$1$ as~$n\to\infty$, all pairs of vertices of~$R'$
  are normal.
\end{lemma}
\begin{proof}
  We prove a few assertions that together imply our lemma.  Below we
  shall use the term `almost surely' to mean `with probability tending
  to~$1$ as~$n\to\infty$.'  Moreover, we shall tacitly assume that~$n$
  is large enough whenever needed. 

  \assertion(A1) Let~$x$ and~$y$ be two points of~$\cP$, and fix a
  line~$L\neq L(x,y)$ that contains~$y$.  Let~$Y=Y(x,y,L)\subset
  L\setminus\{y\}$ be the set of neighbours of~$x$
  within~$L\setminus\{y\}$.  Then the probability that
  \begin{equation}
    \label{eq:Yupbd}
    |Y|<\frac{A\log n}{\log\log n}
  \end{equation}
  holds is at least~$1-n^{-6A/7}$, for any fixed constant~$A$.
  \endassertion
  To prove assertion~(A1), fix a vertex~$z\in L\setminus\{y\}$.
  If~$p$ is the probability that~$x$ and~$z$ are adjacent, then, because
  of~(\ref{eq:n-cond}), we have 
  \begin{equation}
    \label{eq:p-def-bd}
    p=qe(H){\binom{r+1}2}^{-1}\leq bkt^2n^{-1}
      \frac{\log(kt^2)}{\log\log\log(kt^2)}\leq\frac b{\sqrt n}, 
  \end{equation}
  where~$r$ is such that~$n=r^2+r+1$, and, as usual, $e(H)$ denotes
  the number of edges in~$H$.  Now, the events $xz\in E(R')$ ($z\in
  L\setminus\{y\}$) are all independent.  Thus, letting
  $$
  \ell=\llceil\frac{A\log n}{\log\log n}\rrceil,
  $$
  the probability that~(\ref{eq:Yupbd}) fails is at most
  $$
  \binom r\ell p^\ell\leq\(\frac{\e n^{1/2}p}\ell\)^\ell
    \leq\(\frac{\e b}\ell\)^\ell\leq n^{-6A/7},
  $$
  as required.
  
  Note that, in particular, the following assertion holds.
  
  \assertion(A2) If~$A\geq3$, then, almost surely, for all
  triples~$(x,y,L)$ as in~{\rm(A1)}, the set~$Y=Y(x,y,L)$
  satisfies~{\rm(\ref{eq:Yupbd})}.  
  \endassertion
  
  %Clearly, assertion~(A1) implies assertion~(A2) above.
  
  \assertion(A3) Let two points~$x$, $y\in V$ and a constant~$B$ be
  fixed.  Assume that~$Y=Y(x,y,L)$ satisfies~{\rm(\ref{eq:Yupbd})} for
  all lines~$L\neq L(x,y)$ and some fixed~$A$.  Then the number of
  lines~$L\in\cL\setminus\{L(x,y)\}$ that contain a neighbour of
  both~$x$ and~$y$ in~$R'=R'_n(\cP,H,k)$ is less than
  \begin{equation}
    \label{eq:NoLinesUpBd}
    \frac{B\log n}{\log\log\log n}
  \end{equation}
  with probability at least~$1-n^{-6B/7}$.
  \endassertion
  To prove assertion~(A3), first fix a line~$L\neq L(x,y)$.
  Since~(\ref{eq:Yupbd}) holds, in view of~(\ref{eq:p-def-bd}) the
  probability~$\tildep$ that~$L$ contains a common neighbour of~$x$
  and~$y$ satisfies
  \begin{equation}
    \label{eq:ptilde}
    \tildep\leq|Y(x,y,L)|p\leq\frac{Ab\log n}{\sqrt n\log\log n}.
  \end{equation}
  Now, the events $Y(x,y,L)\cap N(y)\neq\emptyset$ $(L\neq L(x,y))$
  are all independent.  Hence, the probability that at least
  $$
  \ell=\llceil\frac{B\log n}{\log\log\log n}\rrceil
  $$
  of these events hold is, in view of~(\ref{eq:ptilde}), at most
  $$
  \binom r\ell\tildep^{\,\ell}
    \leq\(\frac{\e n^{1/2}\tildep}\ell\)^\ell
    \leq n^{-6B/7},
  $$
  as required.
  
  \assertion(A4) If~$B\geq3$, then, almost surely, for all pairs~$x$,
  $y\in V$ of distinct vertices of~$R'=R'_n(\cP,H,k)$, the number of
  lines different from~$L(x,y)$ that contain a common neighbour of~$x$
  and~$y$ is less than the quantity given
  in~{\rm(\ref{eq:NoLinesUpBd}).} 
  \endassertion

  Assertion~(A4) follows immediately from~(A1) and~(A3).

  \assertion(A5) Let~$y$ be a point of~$\cP$, and let~$L\in\cL$
  contain~$y$.  Moreover, suppose that a set~$Y\subset
  L\setminus\{y\}$ is given, and assume that~$Y$
  satisfies~{\rm(\ref{eq:Yupbd})} for some constant~$A$.  Then
  the probability that~$|Y\cap N(y)|\geq11$ is at most~$n^{-11/4}(\log
  n)^{11}$.  
  \endassertion
  The probability that~$|Y\cap N(y)|\geq\ell$ happens is at most the
  probability that a randomly chosen $t'$-element subset~$Z$
  of~$L\setminus\{y\}$ meets~$Y$ in at least~$\ell$ elements,
  where~$t'=t-1$.  Writing~$s$ for the cardinality of~$Y$, we have
  that this latter probability is at most
  \begin{equation*}
    {\binom r{t'}}^{-1}\sum_{i\geq\ell}\binom si\binom{r-s}{t'-i}
      \leq\sum_{i\geq\ell}\binom{t'}i\(\frac sr\)^i,
  \end{equation*}
  which, by~(\ref{eq:Yupbd}) and the trivial lower bounds~$r\geq
  \sqrt n/2$ and~$n\geq t^4$, is seen to be no larger than
  $$
  2\binom t\ell\(\frac{2A\log n}{\sqrt n\log\log n}\)^\ell.
  $$
  Letting~$\ell=11$, assertion~(A5) follows.

  A simple application of assertions~(A1)--(A5) with~$A=B=3$ proves 
  Lemma~\ref{lem:common-nbrs}.
\end{proof}

\subsection{Proof of Lemma~\ref{lem:trees-Random}}
\label{sec:proof-trees-Random}

We are now ready to prove Lemma~\ref{lem:trees-Random}, which,
as remarked above, implies Theorem~\ref{thm:trees}.

\begin{proof}[Proof of Lemma~\ref{lem:trees-Random}]
Let a projective plane~$\cP=(V,\cL)$ on~$n$ points be fixed, and
suppose a $t$-vertex graph~$H$ and an integer~$k$ are given.  Suppose
further that~(\ref{eq:q-def}) and~(\ref{eq:n-cond}) hold.  Consider
the graph~$R'=R'_n(\cP,H,k)$, and suppose that all pairs of distinct
vertices of~$R'$ are normal.  We shall show below that, under these
conditions, we have
\begin{equation}
  \label{eq:R'arrows}
  R'\to(T,H)
\end{equation}
for any tree~$T$ on~$k$ points.  Invoking Lemma~\ref{lem:common-nbrs},
the proof of Lemma~\ref{lem:trees-Random} will be complete.  

To prove~(\ref{eq:R'arrows}), let~$R'$ be red-blue edge-coloured in
such a way that no blue induced copy of~$H$ is present.  Our aim is to
show that, then, any tree~$T$ on at most~$k$ vertices appears as an
induced subgraph of~$R'$ with all its edges coloured red.  To this
end, let us first observe that, since every copy of~$H$ in each line
of~$\cP$ must contain a red edge, there are at least~$qn$ red edges
in~$R'$.  In fact, we may choose exactly~$qn$ red edges in~$R'$ so
that, in each line~$L\in\cL$, we have an independent set of~$q$ red
edges.  Let~$\cR$ be such a collection of red edges.  

A standard argument now shows that there is a subset~$V'$ of~$V(R')$
such that every vertex~$v\in V'$ is incident to at least~$q$ red edges
in~$\cR\cap E(R'[V'])$.  In other words, the graph spanned by~$\cR\cap
E(R'[V'])$ in~$R'[V']$ has minimal degree at least~$q$.  In what
follows, we restrict our attention to~$R'[V']$.

We shall now prove by induction on~$|V(T)|$ that any tree~$T$ on at
most~$k$ vertices is present in~$R'[V']$ as a red induced subgraph.
Thus, $R'[V']$~will be shown to be \textit{red $k$-tree-universal},
that is, all trees on~$k$ vertices appear in~$R'[V']$ as red induced
subgraphs (cf.~the remark following the proof of Lemma~\ref{lem:l4}).

There is nothing to do if~$|V(T)|=1$.  So assume that~$2\leq|V(T)|\leq
k$, and that the subtree~$T'$ of~$T$ obtained from~$T$ by removing a
leaf of~$T$ appears as a red induced subgraph in~$R'[V']$.  (In the
sequel, we identify~$T'$ with this copy of~$T'$ in~$R'[V']$.)
Clearly, it suffices to show that an appropriate vertex~$x'\in
V(T')\subset V'$ has a neighbour~$x\in V'$ such that~$xx'$ is red and,
furthermore, $x$~is not adjacent to any vertex in~$F=T'-x'$.  Let such
a vertex~$x'$ be fixed.

Let
\begin{equation}
  \label{eq:setX}
  Z=\{z\in\NredR(x')\cap V'\:L(x',z)\cap V(F)=\emptyset\}, 
\end{equation}
where~$\NredR(x')$ denotes the set of vertices connected to~$x'$ with
edges in~$\cR$, and~$L(x',z)$ is the line of~$\cP$ determined by~$x'$
and~$z$.  Since there is at most one red edge in~$\cR$ that is
incident to~$x'$ in each line that contains~$x'$, and~$|V(F)|\leq
k-2$, we have that
\begin{equation}
  \label{eq:Zlb}
  |Z|\geq q-k+2\geq\frac12q
    =\frac12bk\frac{\log(kt^2)}{\log\log\log(kt^2)}.
\end{equation}
Using the normality of the pairs~$(x',y)$ for~$y\in V(F)$, we have
that 
\begin{equation}
  \label{eq:FNeighbours}
  \Big|\bigcup_{y\in V(F)}N(y)\cap Z\Big|
   \leq\frac{30(k-2)\log n}{\log\log\log n}.
\end{equation}
Comparing~(\ref{eq:Zlb}) and~(\ref{eq:FNeighbours}) (and recalling
that~$b=200$), we see that there is a vertex~$x\in Z$ that is
\textit{not} adjacent to any vertex in~$F$ in~$R'$.  Thus, we have
found our red induced copy of~$T$ in~$R'[V']$, as required.  This
completes the induction step, and hence we have proved that~$R'[V']$
is indeed red $k$-tree-universal.

As remarked earlier, an application of Lemma~\ref{lem:common-nbrs}
finishes the proof of Lemma~\ref{lem:trees-Random}.
\end{proof}

\section{Concluding Remarks}
\label{sec:final}

A refinement of Theorem~\ref{thm:variant} may be proved in the following
fashion.  As is well known, the technique applied in the proof of
Lemma~\ref{lem:l4} gives better numerical results if the maximum degree of the
graph~$G$ has smaller order of magnitude than~$k=|V(G)|$.  This fact, coupled
with slightly more careful calculations, should suffice to
improve~(\ref{eq:thm:variant}) to
\begin{equation}
  \label{eq:variant_improve}
  \rind(G,H)\leq 2^{c_1k}t^{c_2\Delta\log q}, 
\end{equation}
where~$\Delta=\Delta(G)$ is the maximum degree of~$G$, and~$c_1$ and~$c_2$ are
universal constants. 

However, even with~(\ref{eq:variant_improve}), Problem~\ref{prob:exponential}
and Conjecture~\ref{conj:smallG} remain open. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliographystyle{amsplain}
%\bibliography{/home/mac/yoshi/repts/FAPESP/proj-tematico/proj/refs/refs}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{10}

\bibitem{BeckB}
J.~Beck, \emph{On size {R}amsey number of paths, trees, and circuits~{II}},
  Mathematics of {R}amsey Theory, Algorithms and Combinatorics, vol.~5,
  Springer-Verlag, Berlin, 1990, pp.~34--45.

\bibitem{BrownRodl}
J.I. Brown and V.~R\"odl, \emph{A {R}amsey type problem concerning vertex
  colourings}, Journal of Combinatorial Theory, Series B \textbf{52} (1991),
  no.~1, 45--52, MR92c:05108.

\bibitem{ChvRoSzT}
V.~Chv\'atal, V.~R\"odl, E.~Szemer\'edi, and W.T. Trotter, \emph{The {R}amsey
  number of a graph with bounded maximum degree}, Journal of Combinatorial
  Theory, Series B \textbf{34} (1983), no.~3, 239--243, MR\#85f:05085.

\bibitem{Deu}
W.~Deuber, \emph{A generalization of {R}amsey's theorem}, Infinite and Finite
  Sets (Keszthely, 1973) (A.~Hajnal, R.~Rado, and V.T. S\'os, eds.), Colloquia
  Mathematica Societatis J\'anos Bolyai, vol.~10, North-Holland, 1975,
  pp.~323--332.

\bibitem{eaton92}
N.~Eaton and V.~R{\"o}dl, \emph{A canonical {R}amsey theorem}, Random
  Structures and Algorithms \textbf{3} (1992), no.~4, 427--444.

\bibitem{ErdosPrague74}
P.~Erd{\H o}s, \emph{Problems and results on finite and infinite graphs},
  Recent advances in graph theory (Proc.\ Second Czechoslovak Sympos., Prague,
  1974), (loose errata) Academia, Prague, 1975, MR52\#10500, pp.~183--192.

\bibitem{ErdosCambridge83}
\bysame, \emph{On some problems in graph theory, combinatorial analysis and
  combinatorial number theory}, Graph theory and combinatorics (Cambridge,
  1983) (London, New York) (B.~Bollob\'as, ed.), Academic Press, 1984,
  pp.~1--17.

\bibitem{ErdosHajnalConj}
P.~Erd{\H o}s and A.~Hajnal, \emph{Ramsey-type theorems}, Discrete Applied
  Mathematics \textbf{25} (1989), no.~1--2, 37--52, MR90m:05091.

\bibitem{EHP}
P.~Erd{\H o}s, A.~Hajnal, and L.~P\'osa, \emph{Strong embeddings of graphs into
  colored graphs}, Infinite and Finite Sets (Keszthely, 1973) (A.~Hajnal,
  R.~Rado, and V.T. S\'os, eds.), Colloquia Mathematica Societatis J\'anos
  Bolyai, vol.~10, North-Holland, 1975, pp.~585--595.

\bibitem{GRo}
R.L. Graham and V.~R{\"o}dl, \emph{Numbers in {R}amsey theory}, Surveys in
  Combinatorics~1987 (C.~Whitehead, ed.), London Mathematical Society Lecture
  Note Series, vol. 123, Cambridge University Press, Cambridge--New York, 1987,
  pp.~112--153.

\bibitem{GRS}
R.L. Graham, B.~Rothschild, and J.H. Spencer, \emph{Ramsey theory}, second ed.,
  Wiley-Interscience Series in Discrete Mathematics and Optimization, John
  Wiley {\&} Sons, New York, 1990.

\bibitem{LRo}
T.~{\L}uczak and V.~R{\"o}dl, \emph{On induced {R}amsey numbers for graphs with
  bounded maximum degree}, Journal of Combinatorial Theory, Series B
  \textbf{66} (1996), no.~2, 324--333.

\bibitem{Nesetril95Handbook}
J.~Ne\v{s}et\v{r}il, \emph{Ramsey theory}, Handbook of Combinatorics (R.L.
  Graham, M.~Gr{\"o}tschel, and L.~Lov\'asz, eds.), North-Holland, Amsterdam,
  1995, pp.~1331--1403.

\bibitem{Ram}
F.P. Ramsey, \emph{On a problem of formal logic}, Proceedings of the London
  Mathematical Society \textbf{30} (1930), 264--286.

\bibitem{RoThesis}
V.~R{\"o}dl, \emph{The dimension of a graph and generalized {R}amsey theorems},
  Master's thesis, Charles University, 1973.

\bibitem{rodl86}
\bysame, \emph{On universality of graphs with uniformly distributed edges},
  Discrete Mathematics \textbf{59} (1986), no.~1-2, 125--134.

\bibitem{RodlWinkler}
V.~R\"odl and P.~Winkler, \emph{A {R}amsey-type theorem for orderings of a
  graph}, SIAM Journal on Discrete Mathematics \textbf{2} (1989), no.~3,
  402--406, MR90g:05135.

\end{thebibliography}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
